Novel Complexity Results for Temporal Separators with Deadlines

Here we show that (s,z,$\mathrm{\ell }$)-Temporal Separator can be solved in polynomial time on graphs of pathwidth $3$, for any $\mathrm{\ell }$, which shows that the above hardness is tight, assuming $P\ne NP$. Note that now, we allow temporal edges to have multiple activation times, and we allow them to be directed or not. Let $G$ be a temporal graph. We first apply two reduction rules, which can easily seen to be safe, that is, a solution of size at most $k$ exists in the temporal graph before the application of the rule if and only if it exists also after its application.

We say that $G$ is clean if none of the above rules is applicable to $G$. Note that for $n=|V(G)|$ and $m=|E(G)|$ (note that $E(G)$ is the set of temporal edges of $G$), one can determine in time $O(n+m)$ whether one of the rules applies, and each rule can be applied at most $n$ times, and so a graph can be made clean in time $O(n^2+nm)$. Note, for Rule 1 we assume that the time between the consecutive temporal arcs $(s,v,t),(v,z,t^{\prime })$ can be compared in constant time, and Rule 2 does not use arc times, so there is no time dependency on $\tau$.

We now turn to (clean) graphs of pathwidth at most $3$. We assume that we have checked that $G$ has pathwidth at most $3$ and we can compute a decomposition of $G$ in $O(n)$ time [3]. The idea is to first check whether there is an $(s,z)$-separator of size at most $3$ (so, a separator that ignores edge times). If there is one, then there is an $(s,z,\mathrm{\ell })$-temporal separator of size at most $3$. In this case we can compute a solution by trying every combination of at most three vertices. If there is no such separator, we can rely on the structural lemma below, which is illustrated in Figure 2. First, we can show that there is a sequence of bags that contain both $s$ and $z$; this allows to find $B$, consisting of the vertices introduced and forgotten within this sequence. This $B$ induces a caterpillar⁴⁴4Recall that a caterpillar is a tree in which there is a main path $w_1-\mathrm{\dots }-w_k$, and every vertex not on that path is a leaf adjacent to a vertex of the path. , as removing $s$ and $z$ from these bags yields a subgraph of pathwidth at most $2$. The vertices other than $s$ or $z$ in bags that precede this sequence form $A$, and the vertex $s$ or $z$ introduced last has at most one neighbor in $A$ (e.g., in Figure 2, $z$ has only $y$ as a neighbor in $A$). Analogously, $C$ contains vertices of bags that occur after the sequence.

One can infer from this structure that “most” deletions occur on the caterpillar path.

Our algorithm proceeds as follows. We first make $G$ clean, possibly handling multiple connected components of $G-\{s,z\}$ separately, and construct the sets $A,B,C$ from Lemma 4. We then run Algorithm 1, which first guesses every way that a solution could delete at most one vertex from $A$ and at most one vertex from $C$, noting that such a solution exists by Lemma 5. There are $O(n^2)$ possible guesses, and for each of them, we solve a restricted version of the problem where we can only delete vertices from the caterpillar $B$.

This is done by the $extendSeparator$ function, which attempts to extend the guess by finding the minimum number of deletions to do on the main $B$ path $w_1-\mathrm{\dots }-w_k$, traversing it from left to right. When at a specific $w_i$, we restrict the graph to $G[W_i]-D$, where $D$ contains the deletions made so far and $W_i$ contains $A$, $w_i$ and the predecessors of $w_i$, and their neighbors. In a greedy manner, we delete $w_i$ only if it creates a temporal path in this restricted graph, considering the deletions $D$ applied so far. We can apply a greedy approach, since we can show that no vertex in $N(w_i)$ is removed, if needed $w_i$ is removed instead. This ensures that there is no temporal path that goes through the $w_i$’s in increasing order (possibly going in $A$ as well), and we make one last check at the end to ensure that no temporal path goes through $C$ and then on the path in the reverse order (if so, we delete $w_k$ to prevent that).

Note that the above algorithm works for the strict variant of the problem. Indeed, the algorithm only needs to query whether a forbidden path exists, so it suffices to have access to a routine that determines whether a strict $\mathrm{\ell }$-temporal path exists. Again we leave the details for a future version.

In this section we strengthen the inapproximability of (s,z,$\mathrm{\ell }$)-Strict Temporal Separator (and later we extend the inapproximability to (s,z,$\mathrm{\ell }$)-Temporal Separator). We prove the result by giving an approximation preserving reduction from Directed Multicut to (s,z,$\mathrm{\ell }$)-Strict Temporal Separator. Directed Multicut is known to be inapproximable within factor $2^{\mathrm{\Omega }({\log }^{1-\epsilon }|N|)}$, for any constant $\epsilon >0$, even for a directed acyclic graph with a set $N$ of vertices, unless $NP\subseteq ZPP$ [4]. We recall here that Directed Multicut (we consider it is defined on a directed acyclic graph).

Note that we assume that, for each $(s_i,z_i)\in R$, $i\in [h]$, it holds that $s_i\ne t_i$, otherwise the pair cannot be separated by edge removal. Given an instance $(D,R)$ of Directed Multicut, the vertices that belong to a pair in $R$ are called terminals; the set $R_S$ ($R_Z$, respectively) contains those terminals $v$ such that $v=s_i$ and $(s_i,z_j)\in R$ ($v=z_j$ and $(s_i,z_j=v)\in R$, respectively).

Consider an instance $(D,R)$ of Directed Multicut, in the following we construct a corresponding instance of (s,z,$\mathrm{\ell }$)-Strict Temporal Separator. We first present the idea of the construction. Essentially $G$ contains $|A|+1$ copies of each vertex, plus one vertex for each arc in $A$, in addition to $s$ and $z$. This ensures that only the vertices associated with arcs will be removed, as removing $|A|+1$ copies of each vertex of $D$ requires to delete too many vertices. As for the temporal edges of $G$, for each arc from $u$ to $v$ in $D$, there is a path of length two, consisting of a temporal edge from the vertex associated with $u$ to vertex associated with arc $(u,v)$ and a temporal edge from the vertex associated with arc $(u,v)$ to the vertex associated with $v$. Each vertex $v_i$ is associated with a interval of $\mathrm{\ell }$ timestamps $[\mathrm{\ell }\cdot (2i-2),\mathrm{\ell }\cdot (2i-1)-1]$. The timestamps are assigned to temporal edges of $G$ so that if there exists a path in $D$ from $v_i$ to $v_j$, then there exists a temporal path from two corresponding vertices of $G$, that is $x_{i,q}$ to $x_{j,r}$, $q,r\in [|A|+1]$, with timestamps in the interval $[\mathrm{\ell }\cdot (2i-2),\mathrm{\ell }\cdot (2i-1)-1]$.

Now, we present the formal definition of the instance of (s,z,$\mathrm{\ell }$)-Strict Temporal Separator. First, $\mathrm{\ell }=2|N|$. Given $N=\{v_1,\mathrm{\dots },v_{|N|}\}$, since $D$ is a DAG, we assume that the vertices of $D$ are sorted according to a topological sorting of $D$, that is for $(v_i,v_j)\in A$, $i,j\in [|N|]$, it holds that . We define the set $V$ of vertices:

Now, we define the set of temporal edges. For a vertex $v_i\in N$, $i\in [|N|]$, $Reach(D,v_i)$ denotes the set of vertices that can be reached with a path that starts from $v_i$ in $D$.

Now, we prove the relations between Directed Multicut and (s,z,$\mathrm{\ell }$)-Strict Temporal Separator.

We consider now the (s,z,$\mathrm{\ell }$)-Strict Temporal Separator problem and we present an $(\mathrm{\ell }-1)$-approximation algorithm for it. First, we prove the following easy claim.

Now, we present the approximation algorithm (Algorithm 2). The algorithm greedily looks for a strict $\mathrm{\ell }$-temporal path $P$ between $s$ and $z$. If there exists such a $P$, Algorithm 2 removes all the vertices of $P$ from $G$, except for $s$ and $z$, and adds its vertices to the vertex separator $V^{\prime }$. If there exists no such path, then the algorithm stops and return $V^{\prime }$.

Algorithm 2 has approximation factor $\mathrm{\ell }-1$ since the $\mathrm{\ell }$-temporal paths considered in each iteration are vertex-disjoint, thus any solution of (s,z,$\mathrm{\ell }$)-Strict Temporal Separator contains at least one vertex for each of these temporal path.

Next, we prove that, using an approximation preserving reduction from Vertex Cover $k$-Uniform Hypergraph similar to the one presented in [8] from Set Cover, improving this approximation factor is a challenging problem. In particular, Vertex Cover $k$-Uniform Hypergraph is not approximable within factor $k-\epsilon$, for any positive constant $\epsilon$, assuming the Unique Game Conjecture [13].

We show the APX-hardness of (s,z,$\mathrm{\ell }$)-Temporal Cut, by presenting an approximation preserving reduction from the Multiway Cut problem, which is APX-hard [5]. In this latter problem, the input is an undirected graph $G$ with $k\ge 3$ distinguished vertices $v_1,\mathrm{\dots },v_k$ called terminals. The goal is to remove the minimum number of edges from $G$ to cut all paths between terminals, that is, compute $F\subseteq E(G)$ of minimum size such that in $G-F$ there is no path between $v_i$ and $v_j$ for every distinct $i,j\in [k]$.

Consider an instance $(G,v_1,\mathrm{\dots },v_k)$ of Multiway Cut and construct a temporal graph $H$ as follows. First define $\mathrm{\ell }=k-1$. We assume that some edges of $H$ are undeletable. This can easily be achieved by replacing an undeletable edge $(u,v,t)$ with a large number of parallel paths between $u$ and $v$ at time $t$. We construct $H$ as follows. First, start with a copy of $G$ in which every temporal edge is defined at time $\mathrm{\ell }$, and every such temporal edge is deletable: for each $uv\in E(G)$ we add $(u,v,\mathrm{\ell })$ to $H$. Then add vertices $s$ and $z$, and add the following undeletable edges:

In other words we add $(s,v_i,i)$ and $(v_i,z,\mathrm{\ell }+i)$ for $i\in [k-1]$, and add $(v_k,z,\mathrm{\ell })$. Note that $s$ is a neighbor of every $v_i$ except $v_k$. Also observe that the edge $(v_{k-1},z,\mathrm{\ell }+k-1)$ is useless, but we include it to preserve the pattern.

We present a $2{\log }_2(2\mathrm{\ell })$-approximation algorithm for (s,z,$\mathrm{\ell }$)-Temporal Cut. We start by recalling a generalization of Menger’s Theorem on temporal graphs [2].

Also given a temporal graph $G$, it is possible to compute in polynomial time a minimum temporal $(s,z)$-cut of $G$ [2] and we denote such algorithm by $\mathrm{𝚃𝚎𝚖𝚙𝙲𝚞𝚝}(G)$. We present now a result that will be useful to prove the approximation factor.

We describe now an algorithm that has approximation factor ${\log }_2\tau$, then we show how to use it to achieve approximation factor $2{\log }_2(2\mathrm{\ell })$. We assume for simplicity that $\mathrm{\ell }$ is even.

The algorithm is recursive: given an interval $[a,b]$, at each step if the difference $b-a$ is at least $\mathrm{\ell }-1$, thus $[a,b]$ contains at least $\mathrm{\ell }$ timestamps, it defines a timestamp $t$ that partitions in two (almost) equal parts the intervals of length $\mathrm{\ell }$ contained in $[a,b]$. Then it computes a minimum temporal cut of $G[t-\mathrm{\ell }/2,t+\mathrm{\ell }/2-1]$ and recursively computes a solution on the first part of intervals and a solution on the second part of intervals (independently). Since the number of intervals of length $\mathrm{\ell }$ is bounded by , and each recursive call partitions in two equal parts this set of intervals, it follows that after ${\log }_2\tau$ levels of recursion, the size of an interval is at most $\mathrm{\ell }$, thus there can be at most ${\log }_2\tau$ levels of recursion.

Denote by $h$ the number of recursion levels and by $w_i$ the number of timestamps defined (as $t$ in the pseudocode) at level $i$, $i\in [h]$. Denote by $t_{i,j}$ the $j$-th timestamp chosen by the algorithm at the $i$-th level of the recursion, $i\in [h]$ and $j\in [w_i]$. Now, consider an approximate solution $E^{\prime }$ and optimal solution $Opt$ of (s,z,$\mathrm{\ell }$)-Temporal Cut. We partition $E^{\prime }$ and $Opt$ as follows. Given a timestamp $t_{i,j}$, $i\in [h]$ and $j\in [w_i]$, we denote by $E^{\prime }(t_{i,j})$ the set of temporal edges added to $E^{\prime }$ by the approximation algorithm when it defines $t=t_{i,j}$. By construction and by Lemma 15, the sets $E^{\prime }(t_{i,j})$, $i\in [h]$, $j\in [w_i]$, define a partition of $E^{\prime }$. Similarly, we define $Opt(t_{i,j})$, $i\in [h]$, $j\in [w_i]$, as the set of temporal edges $e\in Opt$ such that (1) there is an $\mathrm{\ell }$-temporal path in $G([t_{i,j}-\mathrm{\ell }/2,t_{i,j}+\mathrm{\ell }/2-1])$ from $s$ to $z$ that contains $e$ and (2) $e$ does not belong to any $Opt(t_{r,q})$, with for some $q\in [w_r]$. Note that by Lemma 15 this is indeed a partition, and in particular for each $i\in [h]$ it holds that $Opt(t_{i,j})\cap Opt(t_{i,q})=\mathrm{\varnothing }$ for each $j,q\in [w_i]$ and $j\ne q$.

Since each temporal edge $e\in Opt$ belongs to exactly one set $Opt(t_{i,j})$ and since $Opt(t_{i,j})\cap Opt(t_{i,q})=\mathrm{\varnothing }$, for each $j,q\in [w_i]$, we have that

and

Now, we prove the following result.

Based on the previous lemma, since the number of recursion levels is bounded by ${\log }_2\tau$, we can prove the following.

Next we prove that the previous approximation algorithm can be used to obtain an approximation algorithm of factor $2{\log }_2(2\mathrm{\ell })$ for (s,z,$\mathrm{\ell }$)-Temporal Cut. We assume that $\tau$ is a multiple of $2\mathrm{\ell }$ (if not, increase $\tau$ to the next multiple of $2\mathrm{\ell }$, with no temporal edges existing in the extra times appended). Consider the time domain $[1,\tau ]$ and computes the following sets of disjoint intervals of $[1,\tau ]$:

• $\mathrm{■}$

  $P_1=\{[1,2\mathrm{\ell }],[2\mathrm{\ell }+1,4\mathrm{\ell }],\mathrm{\dots },[\tau -2\mathrm{\ell }+1,\tau ]\}$;

• $\mathrm{■}$

  $P_2=\{[\mathrm{\ell },3\mathrm{\ell }],[3\mathrm{\ell }+1,5\mathrm{\ell }],\mathrm{\dots },[\tau -3\mathrm{\ell },\tau -\mathrm{\ell }]\}$.

Each interval of length $\mathrm{\ell }$ is contained in at least one element of $P_1$ or $P_2$. and, moreover, two graphs defined on distinct intervals of a set $P_i$ are temporal edge disjoint. Recall that $G(I)$ is the temporal graph defined on interval $I$.

Now, we run Algorithm 3 on each $G(I)$, with $I\in P_i$ and we compute a feasible solution since by Lemma 18 each interval $I$ of length $\mathrm{\ell }$ is contained in an interval of $P_1$ or $P_2$. The $2{\log }_2(2\mathrm{\ell })$-approximation factor is due to the fact that each interval $I$ has length $2\mathrm{\ell }$ and we approximate each with a factor of ${\log }_2(2\mathrm{\ell })$. Then by Lemma 18 two intervals $I$ and $I^{\prime }$ of $P_i$, are temporal edge disjoint, thus each temporal edge removed by an optimal solution belongs to at most one interval of $P_1$ and at most one interval of $P_2$. Because we remove edges from both the intervals in $P_1$ and $P_2$, our approximation factor is multiplied by two.