Temporal Connectivity Augmentation

The problem is in NP, considering that checking connectivity can be done by $O(n^2)$ path computations each in polynomial time [20]. We make a reduction from Dominating Set. In that problem, given a (static) graph $G=(V,E)$ and a positive integer $K$, we want to determine if there is a dominating set of size at most $K$ in $G$, i.e., a subset $V^{\prime }\subseteq V$ with $|V^{\prime }|\le K$ such that for all $u\in V\backslash V^{\prime }$ there is a $v\in V^{\prime }$ for which $\{u,v\}\in E$.

Let $I=(G,K)$ be an instance of DOMINATING SET. We construct $𝒢=(G^{\prime },\lambda )$ a temporal graph (see figure 1) as follows:

• $\mathrm{■}$

  $V^{\prime }=V\cup \{x,y\}$

• $\mathrm{■}$

  $E^{\prime }$ contains edge $\{x,y\}$ and all edges between any two vertices in $V\cup \{y\}$

• $\mathrm{■}$

As we are in the unrestricted case, any temporal edge can be added. The maximal number of temporal edges that we can add is $K$.

We now show that there exists a dominating set for $𝒢$ of size at most $K$ if and only we can make $𝒢$ temporally connected by adding at most $K$ temporal edges.

Let us first make some remarks. The underlying subgraph of $G^{\prime }$ excluding $x$ is complete, meaning that this subgraph is already temporally connected (without adding any edge). Moreover, every vertex $u$ of $V$ can reach $y$ at time 1, hence the journey $u\stackrel{1}{\to }y\stackrel{2}{\to }x$ exists, so we have $u\to x$ for every $u\in V$. Then, to make $𝒢$ temporally connected, we have to ensure that $x\to u$ for all $u\in V$.

• $\Rightarrow$

  Suppose that $U$ is a dominating set for $G$ of size at most $K$. For each $u\in U$, we add the edge $\{x,u\}$ at time 1. Then each vertex $u\in U$ is reachable from $x$ at time 1. As $U$ is a dominating set, each vertex $v\in V\setminus U$ is adjacent to some vertex $u\in U$. Edge $\{u,v\}$ is by construction present at time 2, so $v$ is reachable from $x$. The addition of these $|U|\le K$ temporal edges make the graph connected.

• $\Leftarrow$

  Conversely, suppose that adding a set of at most $K$ temporal edges makes $𝒢$ temporally connected. Suppose that we add a temporal edge between two vertices $u$ and $v$ different from $x$. If it is at time 1 this edge is useless to make $x$ a source. If it is at time $2$, this edge is only useful is there is an edge say $\{x,u\}$ or $\{x,v\}$, say $\{x,u\}$, at time 1. Then we can replace the addition of $(\{u,v\},2)$ by the addition of $(\{x,v\},1)$. This means that adding (only) temporal edges incident to $x$ at time 1 is dominant. Then clearly $(\{x,y\},1)$ is useless. So, let $U$ be the set of vertices in $V$ for which a temporal edge $(\{x,u\},1)$ has been added. Note that $|U|\le K$. Take a vertex $v\in V\setminus U$. By construction of $𝒢$ and definition of $U$, the unique possible path from $x$ to $v$ is through a vertex $u\in U$ at time 1. Then $v$ must be adjacent to $u$ in $V$. $U$ is a dominating set of size at most $K$.

This shows that the unrestricted case is NP-complete. From the above, restricting the augmented set to be in $F=\{(\{x,v)\},1):v\in V\}$ shows NP-hardness for the simple case. $◀$ In the previous reduction, making the graph temporally connected is exactly the same as making $x$ a source of this temporal graph. Thus we derive the following result:

We prove that $𝒫$ is a characterization of temporally connected graphs:

• $\Rightarrow$

  Suppose $𝒢$ is temporally connected. Take $i_1\le k_1$ and $i_T\le k_T$, and consider $u\in C_{i_1}^1$ and $v\in C_{i_T}^T$. We know that there exists a journey from $u$ to $v$. Note that by waiting (in $u$ or in $v$) we can assume without loss of generality that the journey starts (in $u$) at time $1$ and ends (in $v$) at time $T$. At each time step $t$, the journey visits some vertices of a connected component $C_{i_t}^t$ (with $C_{i_1}^1$ containing $u$ and $C_{i_T}^T$ containing $v$). The last vertex visited in $C_{i_{t-1}}^{t-1}$ is by definition both in $C_{i_{t-1}}^{t-1}$ and $C_{i_t}^t$, so the intersection is not empty.

• $\Leftarrow$

  Suppose $𝒢$ verifies $𝒫$, i.e. for every snapshot component at time 1 and at time $T$ we have a sequence of snapshot components starting at 1 and ending at $T$, with a non-empty intersection between consecutive components. For any vertex $u$, we build the journey going to any $v$ with such a sequence. Taking the snapshot component of $u$ at time 1 and the snapshot component of $v$ at time $T$, and then applying the property $𝒫$, gives us a sequence between those two components. Since any consecutive snapshot component in that sequence has a non-empty intersection, that means that at every step we can travel to any vertex that is part of that intersection in the snapshot component to get to the next one. Repeating this until $v$ is reached gives us a journey from $u$ to $v$.

$◀$ On graphs with a lifespan of 2, we get the following corollary:

In other words, every snapshot component at time 1 has to intersect every snapshot component at time 2.

We can now reformulate the unrestricted version of 2-TCA as a problem on a binary matrix. Let us consider a temporal graph $𝒢$ of lifespan 2, with $k_1$ connected components at time 1 and $k_2$ at time 2. We build a matrix $B$, that we call the component-intersection matrix of $𝒢$, with $k_1$ lines and $k_2$ columns, such that $B[i,j]=1$ if $C_i^1$ and $C_j^2$ intersect, and 0 otherwise. Adding a temporal edge $(\{u,v\},1)$ in $𝒢$ corresponds to merging the connected components of $u$ and of $v$ at time 1. On matrix $B$, this corresponds to merging the corresponding rows by an OR-combination. Similarly, adding a temporal edge at time 2 corresponds to merging by an OR-combination the columns corresponding to the components of $u$ and of $v$ at time 2.

In other words, by the construction above the problem can be reformulated as the following one (where combinations can be on rows on or columns).

OR-Combination To One-Filled (OCTO)
Instance: A binary matrix $B$ and a positive integer $K$.
Question: Can $B$ be transformed into a one-filled matrix with at most $K$ OR-combinations?

Interestingly, the following lemma shows that the other direction works as well.

We put one vertex $v_{i,j}$ for each $i,j$ such that $B[i,j]=1$. At time 1, we put all edges $\{v_{i,j},v_{i,j^{\prime }}\}$ for $j\ne j^{\prime }$, so that row $i$ corresponds to a connected component at time 1. At time 2, we put all edges $\{v_{i,j},v_{i^{\prime },j}\}$ for $i\ne i^{\prime }$, so that column $j$ corresponds to a connected component at time 2. $◀$

Now we prove that OCTO is NP-complete.

The problem is trivially in NP. We reduce from the decision version of Disjoint Set Covers [6]. In this problem, we are given a finite set $T=\{e_1,\mathrm{\dots },e_n\}$, a collection $C=\{T_1,\mathrm{\dots },T_m\}$ of subsets of $T$ and a positive integer $K$. We want to determine if $C$ can be partitioned into at least $K$ disjoint parts, such that every part is a cover of $T$.

Let $I=(T,C,K)$ be an instance of DSC. We construct $B$, a binary matrix with $n(m+1)$ rows and $m$ columns as follows: . For $i>n$, the matrix repeats itself, $B[i,j]=B[i-n,j]$.

We claim that $I$ is a YES-instance if and only if $I^{\prime }=(B,m-K)$ is a YES-instance of OCTO.

• $\Leftarrow$

  Suppose $I^{\prime }$ is a YES-instance of OCTO. Then there is a set of $p\le m-K$ OR-combinations of rows or columns that results in a one-filled matrix. Note that the combinations are all on columns, since a meaningful combination on rows has to be done in the $m+1$ copies of the matrix (thus with $m>m-K$ combinations). After the OR combinations of columns, each of the $m-p\ge K$ remaining columns corresponds to OR-combinations of a set of initial rows: let $O=\{\{c_1^1,\mathrm{\dots },c_{k_1}^1\},\mathrm{\dots },\{c_1^{m-p},\mathrm{\dots },c_{k_{m-p}}^{m-p}\}\}$ be the set of combinations done to obtain the columns of the resulting matrix. Since they result from OR combinations, if there is a 1 in some row for some resulting column, that implies that one of the columns used to get that resulting column had a 1 in that row. The matrix is one-filled, so this holds for every resulting column and every row. If we let $𝒞$ be the same set as $O$ but in which we replace each column by the corresponding set in $C$, we get a disjoint partition of $C$, and each element of the partition is a cover for the rows, thus a cover for $T$. The size is given by $m-p\ge K$, hence $I$ is a YES-instance of DSC.

• $\Rightarrow$

  Suppose $I$ is a YES-instance of DSC. Let $P$ be a partition of $C$ into $k\ge K$ part, each part being a disjoint covers of $T$. In the matrix $B$, for every cover, there is a 1 in each row:

  $$\forall j\in \{1,\mathrm{\dots },k\},\forall i\in \{1,\mathrm{\dots },n(m+1)\},\exists l\in P_j:B[i,l]=1$$

  Thus combining the columns in each disjoint cover yields a one-filled matrix. This requires $m-k\le m-K$ combinations, hence $I^{\prime }$ is a YES-instance of OCTO.

$◀$ Together with Lemma 10, from Lemma 11 we derive the following result.

We now look at the source variant in the non-strict setting. The previous result cannot be extended easily like in the previous section; instead we give a separate reduction that proves the following:

The problem is in NP for the same reason as TCA. We make a reduction from Hitting Set.

Hitting Set
Input: A set $S=\{e_1,\mathrm{\dots },e_n\}$, a collection of subsets $C=\{S_1,\mathrm{\dots },S_m\},S_i\subseteq S,\forall i\in \{1,\mathrm{\dots },m\}$ and a positive integer $K\in \mathbb{N}$ with $K\le |S|$.
Question: Is there a subset $S^{\prime }\subseteq S$ with $|S^{\prime }|\le K$ such that $S_i\cap S^{\prime }\ne \mathrm{\varnothing }\forall i\in \{1,\mathrm{\dots },m\}$?

Let $I=(S,C,K)$ be an instance of Hitting Set. We build a temporal graph $𝒢=(G,\lambda )$ as follows (an illustration of this graph is shown in Figure 3). Its vertex set $V$ is composed of:

• $\mathrm{■}$

  A vertex $x$

• $\mathrm{■}$

  For every set $S_j\in C$ that contains the element $e_i$, a vertex $e_i{S}_j$ (this set being referred as $V_{SC}$)

• $\mathrm{■}$

  For every set of $C$, a vertex $S_i$ (this set being referred as $V_C$)

At time 1, the only present edges are between vertices of $V_{SC}$ such that they correspond to the same element $e_i$. At time 2, there is an edge between every $e_i{S}_j\in V_{SC}$ and $S_j\in V_C$.

The reduction is clearly polynomial time. We now prove that there exists a hitting set of $S$ for $C$ with size at most $K$ if and only if there is a set $F^{\prime }$ of at most $K$ temporal edges such that $x$ is a source in $𝒢\uparrow F^{\prime }$.

• $\Leftarrow$

  Suppose that $F^{\prime }$ with $|F^{\prime }|\le K$ is such that $x$ is a source in $𝒢\uparrow F^{\prime }$. We claim that we can build $F^{\prime \prime }$ containing only edges between $x$ and $V_{SC}$ at time 1, such that $x$ is a source in $𝒢\uparrow F^{\prime \prime }$. Suppose there is a temporal edge $(\{u,v\},1)\in F^{\prime }$ with $u,v$ different from $x$. If $x$ cannot reach neither $u$ nor $v$ at time 1, the edge is useless and can also be removed from $F^{\prime }$. Otherwise $x$ can reach $u$ or $v$, say $u$, at time 1 without using $(\{u,v\},1)$. Then $(\{u,v\},1)$ may be useful to reach $v$ at time 1, but we can replace $(\{u,v\},1)$ by $(\{x,v\},1)$ with the same effect. The same reasoning holds for an edge $(\{u,v\},2)\in F^{\prime }$. If $x$ cannot reach neither $u$ nor $v$ at 2 or before, the edge is useless. If $x$ can reach $u$ at some time without using $(\{u,v\},2)$, we can replace the edge by $(\{x,v\},1)$. After these replacements, we have added only temporal edges of the form $(\{x,v\},1)$. To conclude, suppose that we have added an edge $(\{x,S_i\},1)$, with $S_i\in V_C$. The only temporal edges incident to $S_i$ are at time 2 (apart from except $(\{x,S_i\},1)$), meaning that we do not gain more reachability from $x$ by arriving at time 1 at $S_i$ than at time 2. Then we can safely replace $(\{x,S_i\},1)$ by some $(\{x,e_j{S}_i\},1)$ (with $e_j\in S_i$). We build $F^{\prime \prime }$ by applying the described replacements to $F^{\prime }$, and $S^{\prime }$ by taking the corresponding elements of $S$ appearing as endpoints in $F^{\prime \prime }$. Note that $|S^{\prime }|\le K$. To reach a vertex $S_j$, $x$ must use a journey $x\stackrel{1}{\to }{e}_i{S}_j\stackrel{2}{\to }{S}_j$ eventually taking multiple edges in the snapshot component at time 1 containing $e_i{S}_j$. This implies that $e_i\in S_j$, hence $S_j\cap S^{\prime }\ne \mathrm{\varnothing }$. Since every $S_j$ is reachable from $x$, $S^{\prime }$ is a hitting set.

• $\Rightarrow$

  Conversely, suppose that there exists $S^{\prime }\subseteq S$, a hitting set with size at most $K$ for $C$. Then consider $F^{\prime }$ as the set of edges $(\{x,e_i{S}_j\},1)$ for each $e_i\in S^{\prime }$, with $S_j$ chosen arbitrarily. Note that $|F^{\prime }|\le K$. After augmentation, $x$ can reach every $S_j$ that contains at least one element of $S^{\prime }$. Since $S^{\prime }$ is a hitting set, it follows that $x$ can reach all vertices $S_j$. Then at time 2 it can reach all remaining $e_i{S}_j$ from the vertices of $V_C$. Hence $x$ is a source.

This shows NP-hardness for the unrestricted case. From the above, restricting the augmented set to be included in $F=\{(\{x,v\},1),v\in V_{SC}\}$ shows NP-hardness for the simple case.

$◀$

The proof is done by contradiction. Without loss of generality (by symmetry), suppose there are more components at time 1 than the size of the smallest component at time 2. Since the graph is connected, by Lemma 10 each component at time 1 has a non-empty intersection with each component at time 2, including the smallest one. Since there are more snapshot components at time 1 than there are vertices in this smallest component, there are necessarily a vertex in at least two intersections. However, that would imply that it is in both snapshot components at time 1. A vertex in a static graph cannot belong to more than one connected components, hence giving a contradiction. $◀$ This gives the core idea for a polynomial time algorithm. We construct at time 2 stars centered at each vertex of the smallest component of the first time step. Every star has at least a branch to all the other components of the fixed time step. The remaining vertices are arbitrarily linked to the first star, see Algorithm 1 for a pseudocode.

We give a formal proof of optimality:

The algorithm creates $|C_{\mathrm{\ell }}^1|$ stars that correspond to connected components at time 2. By construction, each star intersects all connected components at time 1, hence by Corollary 9 the graph is temporally connected. At time 2, each connected component $C_{i_2}^2$ has $|C_{i_2}^2|-1$ edges (since it is a star), which sums to ${\sum }_{i_2=1}^{|C_{\mathrm{\ell }}^1|}(|C_{i_2}^2|-1)=n-|C_{\mathrm{\ell }}^1|$. Suppose we add $p$ links at time 2, we have $k_2\ge n-p$. To be connected we know $k_2\ge |C_{\mathrm{\ell }}^1|$, where $C_{\mathrm{\ell }}^1$ is the smallest component at time 1, hence $p\ge n-|C_{\mathrm{\ell }}^1|$. $◀$

Let $I=(𝒢,w,X,K,B)$ be an instance of TG-Steiner. Temporal expansion is a classical technique to transform a temporal graph into a static one [19]. We build here a specific expansion that fits our augmentation problem. Let $G_T=(V_T,E_T)$ be (static directed) the graph such that:

• $\mathrm{■}$

  For each vertex $v$ of $𝒢$ we have $T+1$ copies $v^t$, $t=1,\mathrm{\dots },T+1$ in $V_T$. We also have $T$ arcs $(v^t,v^{t+1})$, $t=1,\mathrm{\dots },T$, of weight 0.

• $\mathrm{■}$

  For each temporal edge $(\{u,v\},t)$ of weight $w$ of $𝒢$ we add two vertices $(\{u,v\},t)$ and ${(\{u,v\},t)}^{\prime }$, with an arc of weight $w$ from the former to the latter. We also add 4 arcs of weight 0: from $u^t$ and from $v^t$ to $(\{u,v\},t)$, and from ${(\{u,v\},t)}^{\prime }$ to $u^{t+1}$ and to $v^{t+1}$.

The construction is illustrated in Figure 4. For the set of pairs, if $(u_i,v_i)\in X$ then $(u_i^1,v_i^T)\in X^{\prime }$, i.e. we replace the source by its earliest copy and the sink by its latest copy. We claim that finding a subgraph $H_T$ of $G_T$ of cost $w_T(H_T)\le B$ for which at least $K$ node pairs from the set $X^{\prime }$ are satisfied is equivalent to solving TG-Steiner on $I$.

• $\Rightarrow$

  Suppose there exists such a subgraph $H_T$. Note that the only arcs that have a positive weight are those from $(\{u,v\},t)$ to ${(\{u,v\},t)}^{\prime }$. We take in $𝒢$ all temporal edges $(\{u,v\},t)$ such that $((\{u,v\},t),{(\{u,v\},t)}^{\prime })$ is in $H_T$. In this subgraph of $𝒢$, which has weight at most $K$, the connected pairs are the same as those connected in $H_T$, by construction of our temporal expansion - a path from $u_i^1$ to $v_i^T$ in $H_T$ corresponds to a journey from $u_i$ to $v_i$ in ${𝒢}^{\prime }$. Hence, we are guaranteed to satisfy the same pairs in $H_T$ and ${𝒢}^{\prime }$.

• $\Leftarrow$

  Suppose $I$ is a YES-instance, and let $\mathscr{H}$ be a solution. To construct the solution to the DG-Steiner corresponding instance, the previous process is reversed. We take in $H_T$ all the arcs of weight 0, and arcs $((\{u,v\},t),{(\{u,v\},t)}^{\prime })$ for which the temporal edges $(\{u,v\},t)$ is selected in $\mathscr{H}$. For the same reasons as before, $H_T$ has the same weight as $\mathscr{H}$ and satisfies the same pairs.

$◀$

The previous lemma allows us to use the result of [14]:

By noticing the temporal expansion of a temporal graph has $O(nT+M)$ vertices and $O(nT+M)$ arcs, where $M$ denotes the number of temporal edges of the graph, we get through the reduction an algorithm running in time $O({(nT+M)}^{4p-1}\log (nT+M))$. Hence:

The problem is in NP for the same reason as TCA. We make a reduction from 3-SAT.
Let $x_1,\mathrm{\dots },x_n$ be the variables and $C_1,\mathrm{\dots },C_m$ the clauses of the statement $\varphi$. We construct our transformation graph in two parts.
In the variable part of the graph, we concatenate gadgets that encode the truth value of the variable, and all the edges are at time 1. A gadget has a starting vertex, connected to two other vertices, that we call the true and false buffer vertices. In each branch, we alternate between value vertices and buffer vertices. There is a value vertex in each branch for each clause where the variable appears. The value vertex is connected to the last buffer vertex by an optional link, present at times $\{1,2\}$. The two value vertices are connected to the two following buffer vertices when they exist. The last two value vertices of each branch are connected to the ending vertex of the gadget. The concatenation is done by connecting the ending vertex to the starting vertex of the next variable.
The clause part of the graph has all of its edges at time 2. Like the variable part, the clauses are encoded by a concatenation of gadgets, composed of a starting vertex and an ending vertex. There is an edge for each literal in the clause, from the starting vertex to the buffer preceding the value vertex corresponding to the clause and in the branch corresponding to the literal. There is also an edge from the corresponding value vertex and the ending vertex in the clause part. An example of variable and clause gadgets is shown in figure 5.
We want to connect $x_1^S$ to $x_n^E$ and $C_1^S$ to $C_m^E$. Remark that a path from $x_1^S$ to $x_n^E$ only takes edges at time 1 and is always of cost $3m$. This is because the only edges with cost 1 are those added for each literal in each clause and there are 3 literals per clause. Moreover, for a valid solution of SAT and in a variable gadget, only the edges of one branch are added, implying that exactly $3m$ edges have been added. They connect $x_1^S$ to $x_n^E$ and $C_1^S$ to $C_m^E$. Conversely, if there are no solutions with cost $3m$ then the formula cannot be satisfied.

$◀$ The construction can be adapted for the strict case, however we lose the bound on $T$. Roughly speaking, the path in the variable part is changed from being at time 1 to being a strictly increasing one ending at $\alpha$. Then in the clause part, the path at time 2 is changed to a strictly increasing path starting at $\alpha +1$. This way we preserve the two distinct paths and the proof still holds:

For 2-TCA in the strict setting, we made the observation that only the edges in the augmentation set are interesting to add to the graph. Considering that adding an edge at time 2 is dominated by adding the same edge at time 1, we get that even if we were allowed to add edge-by-edge, the same observation holds. Thus, we get:

As for the non-strict setting, we already establish that the proof is in the unrestricted case by construction. Edge-by-edge would then correspond to allowing doing a column and line merge as one operation, but the optimal solution only does column merges so we would not gain any advantage. It follows then that: