1 Introduction and Motivation

A temporal network is, roughly speaking, a network that changes with time. A great variety of modern and traditional networks are dynamic, e.g., social networks, wireless networks, transport networks. Dynamic networks have been attracting attention over the past years [3, 4, 7, 9, 21], exactly because they model real-life applications. Following the model of [1, 13, 20], we consider discrete time and restrict attention to systems in which the connections between the participating entities may change but the entities remain unchanged. This assumption is clearly natural when the dynamicity of the system is inherently discrete and gives a purely combinatorial flavor to the resulting models and problems.

In several such dynamic settings, maintaining connections may come at a cost; consider a transport network or an unstable chemical or physical structure, where energy is required to keep a link available. We define the cost as the total number of discrete time instances, e.g., days or hours, at which the network links become available, i.e., the sum over all edges of the number of the edge’s availability instances. We focus on design issues of temporal networks that are temporally connected; a temporal network is temporally connected if information can travel over time from any node to any other node following journeys, i.e., paths whose successive edges have strictly increasing availability time instances. If one has absolute freedom to design a small cost temporally connected temporal network on an underlying static network, i.e., choose the edge availabilities, then a reasonable design would be to select a rooted spanning tree and choose appropriate availabilities to construct time-respecting paths from the leaves to the root and then from the root back to the leaves. However, in more complicated scenarios one might not be free to choose edge availabilities arbitrarily but instead specific link availabilities might pre-exist for the network. Imagine a hostile network on a complete graph where availability of a link means a break in its security, e.g., when the guards change shifts, and only then are we able to pass a message through the link. So, if we wish to send information through the network, we may only use the times when the shifts change and it is reasonable to try and do so by using as few of these breaks as possible. In such scenarios, we may need to first verify that the pre-existing edge availabilities indeed define a temporally connected temporal network. Then, we may try to reduce the cost of the design by removing unnecessary (redundant) edge availabilities if possible, without loosing temporal connectivity. Consider, again, the clique network of n vertices with one time availability per edge; it is clearly temporally connected with cost \(\varTheta (n^2)\). However, it is not straightforward if all these edge availabilities are necessary for temporal connectivity. We resolve here the complexity of finding the maximum number of redundant labels in any given temporal graph.

1.1 The Model and Definitions

It is generally accepted to describe a network topology using a graph, the vertices and edges of which represent the communicating entities and the communication opportunities between them respectively. We consider graphs whose edge availabilities are described by sets of positive integers (labels), one set per edge.

Definition 1

(Temporal Graph). Let \(G=(V,E)\) be a (di)graph. A temporal graph on G is an ordered triplet \(G(L)=(V,E,L)\), where \(L=\{L_{e} \subseteq \mathbb {N}:e\in E\}\) is an assignment of labelsFootnote 1 to the edges (arcs) of G. L is called a labeling of G.

Definition 2

(Time Edge). Let \(e=\{u,v\}\) (resp. \(e=(u,v)\)) be an edge (resp. arc) of the underlying (di)graph of a temporal graph and consider a label \(l\in L_e\). The ordered triplet (u, v, l) is called time edge.Footnote 2

Definition 3

(Cost of a Labeling). Let \(G(L)=(V,E,L)\) be a temporal (di)graph and L be its labeling. The cost of L is defined as \(c(L)= \sum _{e\in E} |L_e|\).

A basic assumption that we follow here is that when a message or an entity passes through an available link at time t, then it can pass through a subsequent link only at some time \(t'>t\) and only at a time at which that link is available.

Definition 4

(Journey). A temporal path or journey j from a vertex u to a vertex v ((u, v)-journey) is a sequence of time edges \((u, u_1, l_1)\), \((u_1, u_2, l_2)\), \(\ldots \) , \((u_{k-1}, v, l_k)\), such that \(l_i < l_{i +1}\), for each \(1 \le i \le k - 1\). We call the last time label, \(l_k\), arrival time of the journey.

Definition 5

(Foremost Journey). A (u, v)-journey j in a temporal graph is called foremost journey if its arrival time is the minimum arrival time of all (u, v)-journeys’ arrival times, under the labels assigned to the underlying graph’s edges. We call this arrival time the temporal distance, \(\delta (u,v)\), of v from u.

In this work, we focus on temporally connected temporal graphs:

Definition 6

(Property TC). A temporal (di)graph \(G(L) = (V,E,L)\) satisfies the property TC, or equivalently L satisfies TC on G, if for any pair of vertices \(u,v \in V,~u\not =v\), there is a (u, v)-journey and a (v, u)-journey in G(L). A temporal (di)graph that satisfies the property TC is called temporally connected.

Definition 7

(Minimal Temporal Graph). A temporal graph \(G(L)=(V,E,L)\) over a (strongly) connected (di)graph is minimal if G(L) has the property TC, and the removal of any label from any \(L_e,~e\in E\), results in a \(G(L')\) that does not have the property TC.

Definition 8

(Removal Profit). Let \(G(L)=(V,E,L)\) be a temporally connected temporal graph. The removal profit r(G, L) is the largest total number of labels that can be removed from L without violating TC on G.Footnote 3

1.2 Previous Work and Our Contribution

In recent years, there is a growing interest in distributed computing systems that are inherently dynamic. For example, temporal dynamics of network flow problems were considered in a set of pioneering papers [10, 11, 14, 15]. The model we consider here is a direct extension of the one considered in the seminal paper of [13] and its sequel [20]. In [13], the authors consider the case of one label per edge and examines how basic graph properties change in the temporal setting. In [20], this model is extended to many labels per edge and the number of labels needed for a temporal design of a network to guarantee several graph properties with certainty is examined. The latter also defined the cost notion and, amongst other results, gave an algorithm to compute foremost journeys which can be used to decide property TC. However, the time complexity of that algorithm was pseudo-polynomial, as it was dominated by the cube of the maximum label used in the given labeling. Random edge availabilities were first considered in [1] in order to study the Expected Temporal Diameter of temporal graphs.

Here, we show that if the designer of a temporal graph can select edge availabilities freely, then an almost optimal linear-cost (in the size of the graph) design that satisfies TC can be easily obtained (cf. Sect. 3). We give an almost matching lower bound to indicate optimality. However, there are pragmatic cases where one is not free to design a temporal graph anew, but is given a set of possible availabilities per edge with the claim that they satisfy TC and the constraint that she may only use them or a subset of them for her design. We show that we can verify TC in low polynomial time (cf. Sect. 2). The given design may also be minimal; we partially characterize minimal designs in Sect. 4. On the other hand, there may be some labels of the initial design that can be removed without violating TC (and also result in a lower cost). In this case, how many labels can we remove at best? Our main technical result is that this problem is APX-hard, i.e. it has no PTAS unless \(P=NP\). On the positive side, we show that in the case of complete graphs and random graphs, if the labels are also assigned at random, we can remove all but O(n) labels.

Stochastic aspects and/or survivability of network design were also considered in [12, 18, 19]. An extended report of related work [3–9, 16, 17, 21–23] can be found in our full paper (cf. Appendix).

2 Property TC Is Decidable in Low Polynomial Time

In this section, we give a simple polynomial-time algorithm which, given a temporal (di)graph G(L) and a source vertex s, computes a foremost (s, v)-journey, for every \(v \not = s\), if such a journey exists. Curiously enough, the previously known algorithm was pseudo-polynomial [20]. Our algorithm significantly improves the running time. In fact, we conjecture it is optimal.

Theorem 1

Algorithm 1 satisfies the following, for every vertex \(v\not =s\):

  1. (a)

    If \(arrival\_time[v] < + \infty \), then there exists a foremost journey from s to v, the arrival time of which is exactly \(arrival\_time[v]\). This journey can be constructed by following the parent[v] pointers in reverse order.

  2. (b)

    If \(arrival\_time[v] = + \infty \), then no (s, v)-journey exists.

  3. (c)

    The time complexity of Algorithm 1 is dominated by the sorting time of the set of time edges (resp. time arcs).

Corollary 1

The time complexity of Algorithm 1 is \(O\big (c(L)\cdot \log {c(L)}\big )\).

Conjecture

We conjecture that any algorithm that computes journeys out of a vertex s must sort the time edges (arcs) by their labels, i.e., we conjecture that Algorithm 1 is asymptotically optimal with respect to the running time.

Note that Algorithm 1 can even compute foremost (s, v)-journeys, if they exist, that start from a given time \(t_{start}>0\) onward. Simply, one ignores the time edges (arcs) with labels smaller than the start time.

figure a

3 Nearly Cost-Optimal Design for TC in Undirected Graphs

In this section, we study temporal design on connected undirected graphs, so that the resulting temporal graphs satisfy TC. In this scenario, the designer has absolute freedom to choose the edge availabilities of the underlying graph.

Theorem 2

  1. (a)

    Given a connected undirected graph \(G=(V,E)\) of n vertices, we can design a labeling L of cost \(c(L) = 2(n-1)\) that satisfies the property TC on G. L can be computed in polynomial time.

  2. (b)

    For any connected undirected graph \(G=(V,E)\) of \(n\ge 2\) vertices and for any labeling L that satisfies the property TC on G, the cost of L is \(c(L) \ge 2n-4\).

4 Minimal Temporal Designs

Suppose now that a temporal graph on a (strongly) connected (di)graph \(G=(V,E)\) is given Footnote 4 to a designer with the claim that it satisfies TC. If the given design is not minimal, she may wish to remove as many labels as possible, thus reducing the cost. Minimality of a design can be verified using Algorithm 1.

4.1 Minimal Designs of Non Linear Cost in the Number of Vertices

Notice that if many edges have the same label(s), we can encounter trivial cases of minimal temporal graphs. For example, the complete graph where all edges are assigned the same label is minimal, but there are no journeys of length larger than 1. Here, we focus on minimal temporal graphs, where minimality is not caused merely because of the use of the same labels on every edge. Consider graphs every edge of which only becomes available at most one moment in time and no two different edges become available at the same time. Are there minimal temporal graphs of the above scenario with non linear (in the size of the graph) cost? For example, any complete graph with a single label per edge, different labels to different edges, satisfies TC. Are all these \(\varTheta (n^2)\) labels needed for TC, i.e., are there minimal temporal complete graphs? As we prove in Theorem 4, the answer is negative. However, we give below a minimal temporal graph on n vertices with non-linear in n cost, namely with \(O(n\log {n})\) labels.

A minimal temporal design of \(n \log {n}\) cost

Definition 9

(Hypercube Graph). The k-hypercube graph, commonly denoted \(Q_k\), is the k-regular graph of \(2^k\) vertices and \(2^{k-1} \cdot k\) edges.

Theorem 3

There exists an infinite class of minimal temporal graphs on n vertices with \(\varTheta (n\cdot \log {n})\) edges and \(\varTheta (n\cdot \log {n})\) labels, such that different edges have different labels.

Sketch of Proof. We present a minimal temporal graph on the hypercube. Consider Protocol 2 for labeling the edges of \(G=Q_k\). The temporal graph, G(L), that this labeling procedure produces on the hypercube is minimal.   \(\square \)

figure b

Cliques of at Least 4 Vertices are not Minimal. The complete graph on n vertices, \(K_n\), with a labeling L that assigns a single, different for every edge, label per edge is an interesting case, since \(K_n(L)\) always satisfies TC. However, it is not minimal as the theorem below shows.

Theorem 4

Let \(n\in \mathbb {N},~n\ge 4\) and denote by \(K_n\) the complete graph on n vertices. Any labeling L that assigns a single label to every edge of \(K_n\), different label per edge produces a temporal graph \(K_n(L)\) that is not minimal. In fact, \(\exists S \subseteq \cup _{e\in E(K_n)} L_e,~ |S|= \lfloor \frac{n}{4} \rfloor \), such that when we remove all the labels of S from L, the resulting temporal graph still satisfies TC. Note that by the union \(\cup _{e\in E(K_n)} L_e\) we denote the multiset of all labels used in L.

Proof

The proof is divided in two parts, as follows:

  1. (a)

    We show that the theorem holds for \(K_4\). Without loss of generality, we use labels 1 to 6, one label per edge, and show that we can always remove a label and still satisfy TC. The proof requires an exhaustive check of 720 permutations of the labels and is done via a computer program (code can be found online here: http://cgi.csc.liv.ac.uk/~akridel/research-results.html).

  2. (b)

    Now, consider the complete graph on \(n\ge 4\) vertices, \(K_n=(V,E)\). Partition V arbitrarily into \(\lceil \frac{n}{4} \rceil \) subsets \(V_1, V_2, \ldots , V_{\lceil \frac{n}{4} \rceil }\), such that \(|V_i|=4, \forall i=1,2, \ldots , \lceil \frac{n}{4} \rceil -1 \) and \(|V_{\lceil \frac{n}{4} \rceil }| \le 4\). In each 4-clique defined by \(V_i,~i=1,2,\ldots , \lfloor \frac{n}{4} \rfloor \), we can remove a “redundant” label, as shown in (a). The resulting temporal graph on \(K_n\) still preserves TC since for every ordered pair of vertices \(u,v \in V\):

    • if u, v are in the same \(V_i\), \(i=1,2,\ldots , \lfloor \frac{n}{4} \rfloor \), then there is a (u, v)-journey that uses time edges within the 4-clique on \(V_i\), as proven in (a).

    • if \(u\in V_i\) and \(v\in V_j,~i\not = j\), then there is a (u, v)-journey that uses the (direct) time edge on \(\{u,v\}\).    \(\square \)

4.2 Computing the Removal Profit is APX-hard

Recall that the removal profit is the largest number of labels that can be removed from a temporally connected graph without destroying TC. We now show that it is hard to arbitrarily approximate the value of the removal profit for an arbitrary graph, i.e., there exists no PTASFootnote 5 for this problem, unless P=NP. It is worth noting here that, in our hardness proof below, we consider undirected graphs.

We prove our hardness result by providing an approximation preserving polynomial reduction from a variant of the maximum satisfiability problem, namely from the monotone Max-XOR(3) problem. Consider a monotone XOR-boolean formula \(\phi \) with variables \(x_{1},x_{2},\ldots ,x_{n}\).Footnote 6 The clause \(\alpha =(x_{i}\oplus x_{j})\) is XOR-satisfied by a truth assignment \(\tau \) iff \(x_{i}\ne x_{j}\) in \(\tau \). The number of clauses of \(\phi \) that are XOR-satisfied in \(\tau \) is denoted by \(|\tau (\phi )|\). If every variable \(x_{i}\) appears in exactly k XOR-clauses in \(\phi \), then \(\phi \) is called a monotone XOR( k ) formula. The monotone Max-XOR( k ) problem is, given a monotone XOR(k) formula \(\phi \), to compute a truth assignment \(\tau \) of the variables \(x_{1},x_{2},\ldots ,x_{n}\) that XOR-satisfies the largest possible number of clauses, i.e., an assignment \(\tau \) such that \(|\tau (\phi )|\) is maximized. The monotone Max-XOR(3) problem essentially encodes the Max-Cut problem on 3 -regular (cubic) graphs, which is known to be APX-hard [2].

Lemma 1

[2]. The monotone Max-XOR(3) problem is APX-hard.

Now we provide our reduction from the monotone Max-XOR(3) problem to the problem of computing r(G, L ). Let \(\phi \) be an arbitrary instance of monotone Max-XOR(3) with n variables \(x_{1},x_{2},\ldots ,x_{n}\) and m clauses. Since every variable \(x_{i}\) appears in \(\phi \) in exactly 3 clauses, it follows that \(m=\frac{3}{2}n\). We will construct from \(\phi \) a graph \(G_{\phi }=(V_{\phi },E_{\phi })\) and a labeling \(L _{\phi }\) of \(G_{\phi }\).

For every \(i=1,2,\ldots ,n\) we construct the graph \(G_{\phi ,i}\) and the labeling \(L _{\phi ,i}\) of Fig. 1. In this figure, the labels of every edge in \( L _{\phi ,i}\) are drawn next to the edge. We call the induced subgraph of \(G_{\phi ,i}\) on the 4 vertices \( \{s^{x_{i}},u_{0}^{x_{i}},w_{0}^{x_{i}},v_{0}^{x_{i}}\}\) the base of \( G_{\phi ,i}\). Also, for every \(p\in \{1,2,3\}\), we call the induced subgraph of \(G_{\phi ,i}\) on the 4 vertices \( \{t_{p}^{x_{i}},u_{p}^{x_{i}},w_{p}^{x_{i}},v_{p}^{x_{i}}\}\) the p th branch of \(G_{\phi ,i}\). Finally, we call the edges \(\{ u_{0}^{x_{i}} , w_{0}^{x_{i}} \}\) and \( \{ w_{0}^{x_{i}} , v_{0}^{x_{i}} \}\) the transition edges of the base of \(G_{\phi ,i}\) and, for every \(p\in \{1,2,3\} \), we call the edges \( \{ u_{p}^{x_{i}} , w_{p}^{x_{i}} \}\) and \( \{ w_{p}^{x_{i}} , v_{p}^{x_{i}} \}\) the transition edges of the pth branch of \(G_{\phi ,i}\). For every \(p\in \{1,2,3\}\) we associate the pth appearance of the variable \(x_{i}\) in a clause of \(\phi \) with the pth branch of \(G_{\phi ,i}\).

Fig. 1.
figure 1

The gadget \(G_{\phi ,i}\) for the variable \(x_{i}\).

Full size image

We continue the construction of \(G_{\phi ,i}\) and \(L _{\phi ,i}\) as follows. First, we add an edge between any possible pair of vertices \( w_{p}^{x_{i}},w_{q}^{x_{j}}\), where \(p,q\in \{0,1,2,3\}\) and \(i,j\in \{1,2,\ldots ,n\}\), and we assign to this new edge \( e= \{ w_{p}^{x_{i}} , w_{q}^{x_{j}} \} \) the unique label \(L _{\phi }(e)=\{7\}\). Note here that we add this edge \( \{ w_{p}^{x_{i}} , w_{q}^{x_{j}} \}\) also in the case where \(i=j\) (and \(p\ne q\)). Moreover, we add an edge between any possible pair of vertices \(t_{p}^{x_{i}},t_{q}^{x_{j}}\), where \(i\ne j\), \( i,j\in \{1,2,\ldots ,n\}\), and \(p,q\in \{1,2,3\}\). We assign to this new edge \(e= \{ t_{p}^{x_{i}} , t_{q}^{x_{j}} \}\) the unique label \(L _{\phi }(e)=\{7\}\).

Furthermore we add a new vertex \(t_{0}\) which is adjacent to vertex \( w_{0}^{x_{n}}\) and to all vertices in the set \( \{s^{x_{i}},t_{1}^{x_{i}},t_{2}^{x_{i}},t_{3}^{x_{i}},u_{p}^{x_{i}},v_{p}^{x_{i}}:1\le i\le n,\ 0\le p\le 3\} \). First we assign to the edge \(\{ t_{0} , w_{0}^{x_{n}} \}\) the unique label \( L _{\phi }( \{ t_{0} , w_{0}^{x_{n}} \} )=\{5\}\). Furthermore, for every vertex \( t_{p}^{x_{i}}\), where \(1\le i\le n\) and \(1\le p\le 3\), we assign to the edge \( \{ t_{0} , t_{p}^{x_{i}} \} \) the unique label \(L _{\phi }( \{ t_{0} , t_{p}^{x_{i}} \} )=\{5\}\). Finally, for each of the vertices \(z\in \{s^{x_{i}},u_{p}^{x_{i}},v_{p}^{x_{i}}:1\le i\le n,\ 0\le p\le 3\}\) we assign to the edge \( \{ t_{0} , z \} \) the unique label \(L _{\phi }( \{ t_{0} , z \} )=\{6\}\) . The addition of the vertex \(t_{0}\) and the labels of the (dashed) edges incident to \(t_{0}\) are illustrated in Figure 2(a).

Consider now a clause \(\alpha =(x_{i}\oplus x_{j})\) of \(\phi \). Assume that the variable \(x_{i}\) (resp. \(x_{j}\)) of the clause \(\alpha \) corresponds to the pth (resp. qth) appearance of \(x_{i}\) (resp. \(x_{j}\)) in \( \phi \). Then we identify the vertices \( u_{p}^{x_{i}},v_{p}^{x_{i}},w_{p}^{x_{i}},t_{p}^{x_{i}}\) of the pth branch of \(G_{\phi ,i}\) with the vertices \( v_{q}^{x_{i}},u_{q}^{x_{i}},w_{q}^{x_{i}},t_{q}^{x_{i}}\) of the qth branch of \(G_{\phi ,j}\), respectively (cf. Figure 2(b)). This completes the construction of \(G_{\phi }\) and its labeling \(L _{\phi }\).

Denote the vertex sets \(A= \{s^{x_{i}},u_{p}^{x_{i}},v_{p}^{x_{i}}:1\le i\le n,\ 0\le p\le 3\}\), \( B=\{w_{p}^{x_{i}}:1\le i\le n,\ 0\le p\le 3\}\), and \(C=\{t_{p}^{x_{i}}:1 \le i\le n,\ 1\le p\le 3\}\). Note that \(V_{\phi }=A\cup B\cup C\cup \{t_{0}\}\). Furthermore, for every \(i\in \{1,2,\ldots ,n\}\) and every \(p\in \{1,2,3\}\) we define for simplicity of notation the temporal paths \( P_{i,p}=(s^{x_{i}},u_{0}^{x_{i}},u_{p}^{x_{i}},t_{p}^{x_{i}})\) and \( Q_{i,p}=(s^{x_{i}},v_{0}^{x_{i}},v_{p}^{x_{i}},t_{p}^{x_{i}})\). For every \(i\in \{1,2,\ldots ,n\}\) the graph \(G_{\phi ,i}\) has 16 vertices. Furthermore, for every \(p\in \{1,2,3\}\), the 4 vertices of the p th branch of \(G_{\phi ,i}\) also belong to a branch of \(G_{\phi ,j}\), for some \(j\ne i\). Therefore, together with the vertex \(t_{0}\), the graph \( G_{\phi }\) has in total \(10n+1\) vertices.

Fig. 2.
figure 2

(a) The addition of vertex \(t_{0}\). There exists in \(G_{\phi }\) also the edge \( \{ t_{0} , w_{0}^{x_{n}} \} \) with label \(L _{ \phi }( \{ t_{0} , w_{0}^{x_{n}} \} )=\{5\}\). (b) The gadget for the clause \( (x_{i}\oplus x_{j})\).

Full size image

To provide some intuition about the correctness of Theorem 5, we now briefly describe how we can construct a labeling L of \(G_{\phi }\) by removing \(9n+k\) labels from \(L_{\phi }\), given a truth assignment \(\tau \) of \(\phi \) with \(|\tau (\phi )|\ge k\). First we keep in L all labels of \( L_{\phi }\) on the edges incident to \(t_{0}\). Furthermore we keep in L the label \(\{7\}\) of all the edges \(\{t_{p}^{x_{i}},t_{q}^{x_{j}}\}\) and the label \(\{7\}\) of all the edges \(w_{p}^{x_{i}}w_{q}^{x_{j}}\). Moreover we keep in L the label  \(\{1\}\) of all the edges \( \{t_{p}^{x_{i}},w_{p}^{x_{i}}\}\). Let now \(i=1,2,\ldots ,n\). If \(x_{i}=0\) in \(\tau \), we keep in L the labels of the edges of the paths \( P_{i,1},P_{i,2},P_{i,3}\), as well as the label 1 of the edge \( \{v_{0}^{x_{i}},w_{0}^{x_{i}}\}\) and the label 2 of the edge \( \{w_{0}^{x_{i}},u_{0}^{x_{i}}\}\). Otherwise, if \(x_{i}=1\) in \(\tau \), we keep in L the labels of the edges of the paths \(Q_{i,1},Q_{i,2},Q_{i,3}\), as well as the label 1 of the edge \(\{u_{0}^{x_{i}},w_{0}^{x_{i}}\}\) and the label 2 of the edge \(\{w_{0}^{x_{i}},v_{0}^{x_{i}}\}\).

We now continue the labeling L as follows. Consider an arbitrary clause \( \alpha =(x_{i}\oplus x_{j})\) of \(\phi \). Assume that the variable \(x_{i}\) (resp. \(x_{j}\)) of \(\alpha \) corresponds to the pth (resp. to the qth) appearance of variable \(x_{i}\) (resp. \(x_{j}\)) in \(\phi \). Then, by the construction of \(G_{\phi }\), the pth branch of \(G_{\phi ,i}\) coincides with the qth branch of \(G_{\phi ,j}\), i.e., \( u_{p}^{x_{i}}=v_{q}^{x_{j}}\), \(v_{p}^{x_{i}}=u_{q}^{x_{j}}\), \( w_{p}^{x_{i}}=w_{q}^{x_{j}}\), and \(t_{p}^{x_{i}}=t_{q}^{x_{j}}\). Let \(\alpha \) be XOR-satisfied in \(\tau \), i.e., \(x_{i}=\overline{x_{j}}\). If \(x_{i}= \overline{x_{j}}=0\) (i.e., \(x_{i}=0\) and \(x_{j}=1\)) then we keep in L the label 1 of the edge \(\{v_{p}^{x_{i}},w_{p}^{x_{i}}\}\) and the label 2 of the edge \(\{w_{p}^{x_{i}},u_{p}^{x_{i}}\}\). In the symmetric case, where \( x_{i}=\overline{x_{j}}=1\) (i.e., \(x_{i}=1\) and \(x_{j}=0\)), we keep in L the label 1 of the edge \(\{u_{p}^{x_{i}},w_{p}^{x_{i}}\}\) and the label 2 of the edge \(\{w_{p}^{x_{i}},v_{p}^{x_{i}}\}\). Let now \(\alpha \) be XOR-unsatisfied in \(\tau \), i.e., \(x_{i}=x_{j}\). Then, in both cases where \( x_{i}=x_{j}=0\) and \(x_{i}=x_{j}=1\), we keep in L the label 1 of both edges \(\{v_{p}^{x_{i}},w_{p}^{x_{i}}\}\) and \(\{w_{p}^{x_{i}},u_{p}^{x_{i}}\}\). This finalizes the construction of L from the truth assignment \(\tau \) of \(\phi \).

Theorem 5

There is an assignment \(\tau \) of \(\phi \) with \(|\tau (\phi )|\ge k\) iff \(r(G,L )\ge 9n+k\).

Theorem 6

The problem of computing r(G, L ) on a graph G is APX-hard.

Proof

Denote now by OPT\(_{\text {mon-Max-XOR}(3)}(\phi )\) the greatest number of clauses that can be simultaneously XOR-satisfied by a truth assignment of \( \phi \). Then Theorem 5 implies that \(r(G_{\phi },L _{\phi })\ge 9n+\text {OPT}_{\text { mon-Max-XOR}(3)}(\phi )\). Note that a random truth assignment XOR-satisfies each clause of \(\phi \) with probability \(\frac{1}{2}\), and thus there exists an assignment \(\tau \) that XOR-satisfies at least \(\frac{m}{2}\) clauses of \(\phi \). Therefore OPT\( _{\text {mon-Max-XOR}(3)}(\phi )\ge \frac{m}{2}=\frac{3}{4}n\), and thus, \(n\le \frac{4}{3}\text {OPT}_{\text {mon-Max-XOR}(3)}(\phi )\). Assume that there is a PTAS for computing r(G, L ). Then, for every \(\varepsilon >0\) we can compute in polynomial time a labeling \(L \subseteq L _{\phi }\) for the graph \(G_{\phi }\), such that \(|L _{\phi }\setminus L |\ge (1-\varepsilon )\cdot r(G_{\phi },L _{\phi })\). Given such a labeling \(L \subseteq L _{\phi }\) we can compute by the sufficiency part (\(\Leftarrow \)) of the proof of Theorem  a truth assignment \(\tau \) of \( \phi \) so that \(|L _{\phi }\setminus L |\le 9n+|\tau (\phi )|\) , i.e., \(|\tau (\phi )|\ge |L _{\phi }\setminus L |-9n\). Therefore it follows that:

$$\begin{aligned} |\tau (\phi )|\ge & {} (1-\varepsilon )\cdot r(G_{\phi },L _{\phi })-9n \\\ge & {} (1-\varepsilon )\cdot \left( 9n+\text {OPT}_{\text {mon-Max-XOR} (3)}(\phi )\right) -9n \\\ge & {} (1-\varepsilon )\cdot \left( \text {OPT}_{\text {mon-Max-XOR}(3)}(\phi )\right) -9\varepsilon \cdot \frac{4}{3}\text {OPT}_{\text {mon-Max-XOR} (3)}(\phi )\\= & {} (1-13\varepsilon )\cdot \left( \text {OPT}_{\text {mon-Max-XOR}(3)}(\phi )\right) \end{aligned}$$

That is, assuming a PTAS for computing r(G, L ), we obtain a PTAS for the monotone Max-XOR(3) problem, which is a contradiction by Lemma 1, unless \(P=NP\). So, computing r(G, L ) on an undirected graph G is APX-hard.    \(\square \)

4.3 Random Labelings on Dense Graphs Have High Removal Profit

We show here that dense graphs with random labels satisfy TC and have a very high removal profit with high probability (whp).

Definition 10

We call normalized uniform random temporal graph any graph on \(n \in \mathbb {N}\) vertices, each edge of which receives exactly one label uniformly at random, and independently of other edges, from the set \(\{1,\ldots , n\}\).

Theorem 7

  1. (a)

    In the normalized uniform random temporal clique of n vertices, we can delete all but \(2n + O(\log {n})\) labels without violating TC whp.

  2. (b)

    Let \(G=(V,E)\) be an instance of the Erdös-Renyi model of random graphs, \(G_{n,p}\), with \(p \ge \frac{a\sqrt{n}\log {n}}{n}\), where a is constant, and consider a normalized uniform random temporal graph, G(L), on G. We can delete all but \(2n + O(\sqrt{n})\) labels of G(L) without violating TC whp.

Sketch of Proof. We provide a sketch of the proof of (a). Partition the set of available labels \(\{1,2, \ldots , n\}\) into 4 consecutive equisized subsets \(A_1, \dots , A_4\). Each edge receives a single random label l, with \(Pr[l \in A_i] = \frac{1}{4},~\forall i=1,2,3,4\). Color green(g), yellow(y), blue(b) and red(r) the edges that are assigned a label in \(A_1\), \(A_2\), \(A_3\) and \(A_4\) respectively. A temporal router is a subgraph of the clique consisting of a central vertex with a number of yellow incident edges and a number of blue incident edges. Fix a vertex u of the graph. By use of Chernoff bounds, we show the following:

Lemma 2

There is a set \(S_1\) of at least \(\frac{n}{4}\) yellow edges incident to u and a set \(S_2\) of at least \(\frac{n}{4}\) blue edges incident to u, with probability at least \(1 - 2 e^{-\frac{n}{16}}\).

Conditioning on the above property of u, we arbitrarily select a subset \(D_i\) of \(S_i\) with \(|D_i|= \alpha \log {n},~i=1,2\). \(R=D_1 \cup D_2 \cup \{u\}\) is then a \(O(\log {n})\)-size temporal router.

Lemma 3

Any vertex \(w\in V \setminus R\) has an incident g edge to a vertex in \(D_1\) and an incident r edge to a vertex in \(D_2\) with probability at least \(1 -2 e^{- \frac{\alpha \log {n}}{4} } \).

Using Lemma 3, we show that whp, we can remove all the labels from the random labeling on the graph except for the labels on the edges of the “router” and the two incident edges of any \(w \in V\), one g connecting it to a vertex in \(D_1\) and one r connecting it to a vertex in \(D_2\), and still satisfy the property TC.    \(\square \)