Robust Temporal Cut

In this paper, we introduce and study the classical and parameterized complexity of RTC. In Section 3, we show that RTC is NP-complete even if $k=1$ and $\delta =1$. In other words, even if the adversary can only modify a single time edge by changing its time label by $1$, RTC is NP-complete. We also show $W[1]$-hardness for the parameter solution size and for the parameter vertex interval membership width plus pathwidth. Then, in Section 4, we present FPT algorithms for several parameters: vertex cover number of the underlying graph plus solution size, timed vertex cover number, and temporal neighborhood diversity plus solution size. In Section 5, we consider approximation algorithms for MinRTC. We show that there is a $(2\delta +1)$-approximation algorithm for the case where $k$ is so large that the adversary can modify an arbitrary number of time labels and a $(k(2\delta +1)+1)$-approximation algorithm for arbitrary $k$ and $\delta$. Our results hold for directed and undirected temporal graphs, and regardless of whether strict or non-strict journeys are being considered. The proofs of statements marked with ($\star$) have been omitted due to space restrictions.

Akrida et al. [2] study maximum temporal $s$-$z$ flows and minimum temporal $s$-$z$ cuts in temporal graphs. They show that a maximum $s$-$z$ flow can be computed in polynomial time, even if the nodes have finite buffer capacities, either by solving a linear program or by computing a standard maximum flow in the time-expanded network. For the case that the nodes have infinite buffers, they show that the capacity of a minimum temporal $s$-$z$ cut (the sum of the capacities of the time edges in the cut) equals the value of a maximum temporal $s$-$z$ flow, and both can be computed in polynomial time by running a standard maximum flow or minimum cut algorithm in the time-expanded network. In this paper, we generalize the notion of minimum temporal $s$-$z$ cuts to the robust setting where an adversary can change the time labels of some edges.

Zschoche et al. [17] study the problem of finding a smallest $s$-$z$ separator in a temporal graph, i.e., a smallest set of vertices of the underlying graph whose removal destroys all $s$-$z$ journeys. They assume that all time labels are positive integers and show that the problem is NP-hard except when the lifetime of the given temporal graph is very small (at most $4$ for strict paths and at most $1$ for non-strict paths). They also consider the case that the underlying graph is planar or the temporal core has constant size. Fluschnik et al. [11] show that the problem is polynomial if the underlying graph has bounded treewidth but NP-hard for various other restrictions on the underlying graph. Other questions in relation to temporal cuts and disjoint temporal paths have also been studied, see e.g. [5, 14, 15].

Settings where time labels of the given temporal graph can be modified have recently been studied by several authors: Füchsle et al. [12] consider the problem of identifying a temporal $s$-$z$ path that remains a journey even if an adversary changes up to $k$ time labels or traversal times by up to $\delta$. They show that the problem is NP-hard and present W[1]-hardness results and FPT algorithms for different parameters. Enright et al. [10] study reachability questions in this setting. In particular, they show that the following problem is NP-complete: Given a temporal graph $𝒢$ and positive integers $k,\delta ,h$, is it possible to change the time labels of at most $k$ time edges by adding a value in the range $[-\delta ,\delta ]$ in such a way that the resulting temporal graph has a vertex that can reach at least $h$ vertices via temporal paths? Kutner and Sommer [16] consider a temporal graph $𝒢$ given together with a number of passenger requests (specifying start vertex, end vertex, and desired arrival time) and study the problem of deciding whether it is possible to delay some time edges by at most $\delta$ in such a way that all passenger requests can be satisfied. They show that the problem is polynomial if the underlying graph is a tree but NP-hard in general.

A problem in static graphs that turns out to be related to the RTC problem is Length-Bounded Cut: Given a graph $G=(V,E)$ with designated source $s$ and destination $z$ as well as a length bound $\mathrm{\ell }$, remove a minimum number of edges (or vertices) so that the resulting graph has no $s$-$z$ path of length at most $\mathrm{\ell }$. Baier et al. [3] show that the problem is NP-hard and APX-hard for $\mathrm{\ell }\ge 4$ for edge cuts and for $\mathrm{\ell }\ge 5$ for vertex cuts, no matter whether $G$ is directed or undirected. Golovach and Thilikos [13] study the parameterized complexity of Length-Bounded Cut problems. They show parameterized hardness for the parameter $a$ (the size of the cut) and give an FPT algorithm in the parameter $\mathrm{\ell }+a$; their results apply to both directed and undirected graphs. Additionally, Dvořák and Knop [8] show W[1]-hardness with respect to the pathwidth of the (undirected) input graph. We adapt the hardness results for Length-Bounded Cut from [3, 13, 8] to derive hardness results for RTC.

Assume that the time labels of $𝒢$ lie in $[1,L]$. Construct a dynamic programming table with entries $D[u,b,t]$ for $u\in V$, $0\le b\le k$, and $1-\delta \le t\le L+\delta +1$. At the end of the computation, an entry $D[u,b,t]$ has value $1$ if $u$ can be reached before time $t$ by a journey from $s$ that contains at most $b$ $\delta$-modified time edges, and value $0$ otherwise.

First, consider the case of directed temporal graphs and strict temporal paths. We initialize $D[s,t,b]=1$ for all $1-\delta \le t\le L+\delta +1$ and $0\le b\le k$ and set all other entries to $0$. In each round, we update the table entries as follows:

• $\mathrm{■}$

  For every time edge $(uv,t)\in ℰ$ and every $b$ with $0\le b\le k$ such that $D[u,b,t]=1$, set $D[v,b,t^{\prime \prime }]=1$ for all $t^{\prime \prime }$ with $t+1\le t^{\prime \prime }\le L+\delta +1$. This update corresponds to using a journey containing up to $b$ $\delta$-modified time edges to reach $u$ before time $t$ and then following the time edge $(uv,t)$.

• $\mathrm{■}$

  For every time edge $(uv,t)\in ℰ$ and every $t^{\prime }\ne t$ with $t-\delta \le t^{\prime }\le t+\delta$ and every $b$ with such that $D[u,b,t^{\prime }]=1$, set $D[v,b+1,t^{\prime \prime }]=1$ for all $t^{\prime \prime }$ with $t^{\prime }+1\le t^{\prime \prime }\le L+\delta +1$. This update corresponds to using a journey containing $b$ $\delta$-modified time edges to reach $u$ before time $t^{\prime }$ and then following the $\delta$-modified time edge $(uv,t^{\prime })$.

As no journey can consist of more than $n-1$ time edges, the entries of $D$ are correct after at most $n-1$ rounds. The input is $(k,\delta )$-safe if and only if $D[z,b,L+\delta +1]=0$ for all $0\le b\le k$.

If $D[z,b,L+\delta +1]=1$ for some $b$, a sequence of time edges that can be turned, by a $(k,\delta )$-modification, into an $s$-$z$ journey can be determined using traceback.

The proof for undirected temporal graphs and/or non-strict journeys is similar. $◀$

Lemma 4 implies that RTC is contained in NP. Therefore, all problem variants that we prove to be NP-hard in the remainder of this paper are in fact NP-complete.

An FPT algorithm for a decision problem parameterized by a parameter $\omega$ is an algorithm that solves the problem in $f(\omega )\cdot {|x|}^{𝒪(1)}$ time, where $f$ is a computable function and $|x|$ denotes the size of the input. Showing a parameterized problem to be W[1]-hard is considered strong evidence that the problem does not admit an FPT algorithm. We refer to standard textbooks (e.g., [7]) for further information on parameterized complexity.

An algorithm for a minimization problem is a $\rho$-approximation algorithm if it runs in polynomial time and always outputs a solution whose objective value is at most a factor of $\rho$ larger than that of the optimal solution.

A path decomposition [7] of an undirected graph $G=(V,E)$ is a sequence $(B_1,\mathrm{\dots },B_r)$ of bags such that:

• $\mathrm{■}$

  for each $i\in [1,r]$, $B_i\subseteq V$,

• $\mathrm{■}$

  for each edge $e\in E$, there is at least one index $i\in [1,r]$, such that $e\subseteq B_i$, and

• $\mathrm{■}$

  for each vertex $v\in V$, the subsequence of bags that contain $v$ is consecutive, that is, $v\in B_i$ for each $i\in [\mathrm{\ell },h]$ with $\mathrm{\ell }=\min \{j\in [1,r]\mid v\in B_j\}$ and $h=\max \{j\in [1,r]\mid v\in B_j\}$.

The width of a path decomposition $(B_1,\mathrm{\dots },B_r)$ is defined as the size of the largest bag minus one, that is, $\max \{|B_i|\mid i\in [1,r]\}-1$. The pathwidth of a graph $G$ is the minimum width of any path decomposition of $G$.

A vertex cover of an undirected graph $G=(V,E)$ is a set $S$ of vertices, such that for each edge $e\in E$, at least one endpoint is in $S$, that is, $e\cap S\ne \mathrm{\varnothing }$. The vertex cover number of $G$ is the size of the smallest vertex cover of $G$.

For an undirected temporal graph $𝒢=(V,ℰ)$ with time labels in $[1,L]$, a pair $(v,t)$ of a vertex $v\in V$ and a time step $t$ with $1\le t\le L$ is called a time vertex. A timed vertex cover of $𝒢$ is a set $C$ of time vertices with the property that for every time edge $(uv,t)\in ℰ$, either $(u,t)\in C$ or $(v,t)\in C$. Note that this requires at least one time vertex from each time step at which there are active edges, and so the size of a timed vertex cover is typically lower bounded by the lifetime of a temporal graph. The timed vertex cover number of a temporal graph is the size of a smallest timed vertex cover. It is equal to the sum of the vertex cover numbers of the graphs present in each time step of $𝒢$.

Let $𝒢=((V,E),\lambda )$ be a temporal graph of lifetime $L$. For each vertex $v\in V$, we define the activity interval $I_v$ of $v$ as the interval of time steps $[{\alpha }_v,{\beta }_v]$, where ${\alpha }_v:=\min \{\lambda (e)\mid e\in E,v\in e\}$ and ${\beta }_v:=\max \{\lambda (e)\mid e\in E,v\in e\}$ are the first and last time steps respectively in which $v$ has an incident time edge. The vertex-interval-membership width (vim width) [6] of $𝒢$ is the size of a largest set of vertices $S\subseteq V$, such that all of them are active at some common time step, that is, ${\bigcap }_{v\in S}[{\alpha }_v,{\beta }_v]\ne \mathrm{\varnothing }$.

The timed neighborhood of a vertex $v$ in an undirected temporal graph $𝒢=(V,ℰ)$ is defined as the set $\{(u,t)\mid u=v\text{ or }\exists (vu,t)\in ℰ\}$. For a set $U\subseteq V$ with $v\in U$, the timed neighborhood of $v$ outside $U$ is defined as the set $\{(w,t)\mid w\notin U\text{ and }\exists (vw,t)\in ℰ\}$.

For a vertex $v$ in an undirected temporal graph $G=(V,ℰ)$ with lifetime $L$, the (open) neighborhood of $v$ at time $t$ is $N_t(v)=\{(u,t)\mid (vu,t)\in ℰ\}$. The temporal neighborhood diversity [9] of $𝒢=(V,ℰ)$ is defined as the minimum number of parts in a partition of $V$ for which every part $X$ satisfies the following property: At every time $t$, $N_t(v)\setminus \{(u,t)\}=N_t(u)\setminus \{(v,t)\}$ for all $u,v\in X$. In other words, all vertices in $X$ have the same timed neighborhood outside $X$, and the subgraph induced by $X$ is either a clique or an independent set in each time step. The temporal neighborhood diversity of $𝒢$ can be computed in polynomial time [9].

Let $I:=(G=(V,E),s,z,c,\mathrm{\ell })$ be an instance of Length-Bounded Cut. Let $G^{\prime }=(V^{\prime },E^{\prime })$ be the graph obtained by

• $\mathrm{■}$

  adding a new vertex $z^{\prime }$ to $G$ and

• $\mathrm{■}$

  connecting $z$ with $z^{\prime }$ by $c+1$ vertex-disjoint paths $P_i^z$ of length $\mathrm{\ell }+1$ with new vertices.

We call $(G^{\prime },s,z^{\prime })$ the natural extension of $I$.

Now, consider any edge labeling $\lambda$ that assigns one label per edge of $G^{\prime }$ such that

1. 1.

   no edge receives a label in $[1,\mathrm{\ell }]$,

2. 2.

   for each path $P_i^z$, the labels of the edges are strictly increasing going from $z$ to $z^{\prime }$, and

3. 3.

   all labels assigned to any other edge (that is, the edges of $E$), are larger than any label assigned to any edge of any $P_i^z$.

We call such a labeling a natural extension labeling of $I$.

Note that $\delta$ can be assumed to be at most $n$ plus the largest label assigned by $\lambda$ due to Lemma 3, so that we in fact have an integer value for $\delta$.

$(\Rightarrow )$ Let $F$ be a set of at most $c$ edges such that there is no path of length at most $\mathrm{\ell }$ from $s$ to $z$ in $G-F:=(V,E\setminus F)$. Then, as each edge only receives a single label under $\lambda$, we can remove all occurrences of all edges of $F$ in $𝒢:=(G^{\prime },\lambda )$ by removing at most $c=a$ time edges. Let ${𝒢}^{\prime }$ be the resulting temporal graph. We show that ${𝒢}^{\prime }$ is $(k,\delta )$-safe. Assume towards a contradiction that there is a $(k,\delta )$-modification ${𝒢}^{\ast }$ of ${𝒢}^{\prime }$ that contains an $s$-$z^{\prime }$-journey $J$. By construction, each path from $s$ to $z^{\prime }$ in $G^{\prime }$ starts with a path $P^{\ast }$ from $s$ to $z$ in $G$ and ends with a path $P_i^z$. In particular, this implies that in ${𝒢}^{\ast }$, there is a temporal $s$-$z^{\prime }$-path that can be decomposed like this. As each path $P_i^z$ has length at least $\mathrm{\ell }+1>k$, at least one edge of $P_i^z$ was not modified. Since each label assigned to any edge of $E$ is larger than each label assigned to edges of $P_i^z$, this implies that all edges of the path $P^{\ast }$ from $s$ to $z$ were modified. This, however, contradicts the fact that there is no path of length at most $k=\mathrm{\ell }$ from $s$ to $z$ in $G-F$. Hence, ${𝒢}^{\prime }$ is $(k,\delta )$-safe.

$(\Leftarrow )$ Let ${ℱ}^{\prime }$ be a set of at most $c$ time edges such that $𝒢\setminus {ℱ}^{\prime }$ is $(k,\delta )$-safe. Let $F:=\{e\in E\mid \exists t:(e,t)\in {ℱ}^{\prime }\}$. We show that there is no path of length at most $\mathrm{\ell }=k$ from $s$ to $z$ in $G-F$. Assume towards a contradiction that there is a path $P$ of length $q\le \mathrm{\ell }$ from $s$ to $z$ in $G-F$. We denote the $i$th edge of $P$ by $e_i$. As there are more than $c$ edge-disjoint paths $P_i^z$ from $z$ to $z^{\prime }$, one of these paths is completely part of $𝒢\setminus {ℱ}^{\prime }$. By definition of the natural extension labeling, the label $\beta$ of the first edge of $P_i^z$ is at least $\mathrm{\ell }+1$ (Condition 1). Now, consider the modification of $𝒢\setminus {ℱ}^{\prime }$, where we change the label of edge $e_i$ of $P$ to $i$ for each $i\in [1,q]$. As $q\le \mathrm{\ell }=k$ and $\delta$ is sufficiently large, this is possible within the budget $(k,\delta )$. Hence, in the resulting temporal graph, there is a temporal path from $s$ to $z$ that ends at time . Combining this path with the path $P_i^z$, we obtain a temporal $s$-$z^{\prime }$-path in the resulting temporal graph, which contradicts the fact that $𝒢\setminus {ℱ}^{\prime }$ is $(k,\delta )$-safe. As a consequence, we conclude that $G-F$ contains no path of length at most $\mathrm{\ell }$, which shows that $I$ is a yes-instance of Length-Bounded Cut.

Observe that it is immaterial in the arguments above whether we consider strict or non-strict journeys and that $G^{\prime }$ is directed or undirected depending on whether $I$ is a directed or undirected instance of Length-Bounded Cut. $◀$ This reduction has several implications: First of all, we obtain hardness of RTC in general, as Length-Bounded Cut is NP-hard [3] and W[1]-hard when parameterized by $c$ (the number of edges to remove) [13].

Moreover, as a natural extension labeling has nearly no restrictions on the labels of the edges of $G$, we can use this to show hardness also when parameterized by interval-membership width parameters. This is due to the fact that Length-Bounded Cut is W[1]-hard when parameterized by the pathwidth of the graph [8], which has a natural relation to the vertex-interval-membership width $\mathrm{vimw}$.

Let $I:=(G=(V,E),s,z,c,\mathrm{\ell })$ be an instance of Length-Bounded Cut. We show that there is a natural extension labeling that has a vim width bounded by a linear function in the pathwidth of the underlying graph. In the same argument, we will also show the bound on the pathwith of the natural extension.

Let $(B_1,\mathrm{\dots },B_r)$ be a path decomposition of the input graph $G$ of minimal width $\omega$. We will use this path decomposition to define the natural extension labeling with a small vim width. To this end, we first define a sequence of vertex subsets $(W_1,\mathrm{\dots },W_q)$, where $q=\mathrm{\ell }+(c+1)(\mathrm{\ell }+1)+r$, such that for each $i$, $W_i$ contains (a superset of) all vertices $v$ for which $i\in [{\alpha }_v,{\beta }_v]$. Here, $[{\alpha }_v,{\beta }_v]$ is the activity interval of $v$, that is, ${\alpha }_v$ and ${\beta }_v$ are the smallest and largest label incident with vertex $v$.

Note that $(W_1,\mathrm{\dots },W_q)$ immediately gives a path decomposition of the underlying graph. Each set $W_i$ will contain the vertices $\{s,z,z^{\prime }\}$. The first $\mathrm{\ell }$ sets will contain only the vertices $\{s,z,z^{\prime }\}$ and no edge will receive any label from $[1,\mathrm{\ell }]$, thus satisfying Condition 1 for a natural extension labeling. In the following $(c+1)(\mathrm{\ell }+1)$ sets, we will deal with the internal vertices from the paths $P_i^z$. That is, $W_{\mathrm{\ell }+(i-1)\cdot (\mathrm{\ell }+1)+j}=\{s,z,z^{\prime }\}\cup e_{i,j}$, where $e_{i,j}$ is the $j$th edge of path $P_i^z$. Moreover, edge $e_{i,j}$ then receives label $\mathrm{\ell }+(i-1)\cdot (\mathrm{\ell }+1)+j$. No other set will contain an internal vertex of any of the paths $P_i^z$. This ensures that Condition 2 for a natural extension labeling is satisfied.

It remains to deal with all edges of $E$. To this end, recall that $(B_1,\mathrm{\dots },B_r)$ is a path decomposition of $G=(V,E)$. We define $W_{\mathrm{\ell }+(c+1)(\mathrm{\ell }+1)+i}$ as $\{s,z,z^{\prime }\}\cup B_i$ for each $i\in [1,r]$, and we assign label $\mathrm{\ell }+(c+1)(\mathrm{\ell }+1)+i$ to all edges of $G[B_i]$ that have not yet received a label. This implies that each edge of $E$ receives a label strictly larger than the largest label assigned to any edge of any path $P_i^z$, which ensures that Condition 3 for a natural extension labeling is satisfied.

Hence, the resulting labeling $\lambda$ is in fact a natural extension labeling, and the sets $(W_1,\mathrm{\dots },W_{\mathrm{\ell }+(c+1)(\mathrm{\ell }+1)+r})$ verify that both the pathwidth and the vim width of the temporal graph do not exceed $\omega +𝒪(1)$. The W[1]-hardness for RTC for these parameters then follows by Lemma 5 and the fact that Length-Bounded Cut is W[1]-hard when parameterized by the pathwidth [8]. $◀$

We can derive hardness results for constant values of $k$ by the natural extension reduction, but we will show a clear dichotomy for the values of $k$ and $\delta$ in the following by reducing from Vertex Cover. In these reductions, we adapt the gadget used by Baier et al. [3] to show hardness for Length-Bounded Cut.

First, consider directed temporal graphs. We give a reduction from Vertex Cover.

Vertex Cover
Input: A graph $G$ and an integer $c$.
Question: Is there a vertex cover of size at most $c$ for $G$?

Let $(H=(V_H,E_H),c)$ be an instance of Vertex Cover and let $n=|V_H|$. Moreover, let $\delta >0$ be arbitrary. We construct an instance $I^{\prime }=((G,\lambda ),s,z,a=n+c,k=1,\delta )$ of RTC as follows (see Fig. 1 for an illustration). The underlying graph $G=(V,E)$ has the following vertices: a vertex $s$, a vertex $z$, vertices $u_1,u_2,u_3,u_4$ for every $u$ in $V_H$, and vertices $x_{uv},x_{vu}$ for every $\{u,v\}\in E_H$. The edge set $E$ contains the following edges: For each $u\in V_H$, it contains the directed edges $s{u}_1$,$u_1{u}_2$, $u_2{u}_3$, $u_3{u}_4$ and $u_{4}z$ (referred to as the vertex path for $u$) as well as $s{u}_2$ and $u_{3}z$ (referred to as shortcuts of $u$). For every $\{u,v\}\in E_H$, it contains the directed edges $u_2{x}_{uv}$ and $x_{uv}{v}_3$ as well as $v_2{x}_{vu}$ and $x_{vu}{u}_3$ (referred to as cross paths between $u$ and $v$). Note that $G$ is a DAG. The vertex path of $u$ together with the shortcuts of $u$ is called the vertex gadget of $u$.

The time labels of the edges on the vertex paths are set to $1,2,2,2,3$ and those of the cross paths to $1,2$ (in the order of the paths). The shortcut edges with tail $s$ have time label $0$, and the shortcut edges with head $z$ have time label $4$.

We claim that $I^{\prime }$ is a yes-instance of RTC if and only if $I$ is a yes-instance of Vertex Cover.

$(\Leftarrow )$ Let $C\subseteq V_H$ be a vertex cover of $H$ with size at most $c$. Consider the set $ℱ$ of time edges that contains for every $u\in C$ the two shortcuts of $u$ and for every $u\notin C$ the time edge $(u_2{u}_3,2)$. $ℱ$ has size $n+|C|\le n+c=a$. We claim that $ℱ$ is a robust cutset. First, observe that the vertex gadget of every vertex $u\in V_H$ is $(1,\delta )$-safe: If $(u_2{u}_3,2)\in ℱ$, the gadget contains no $s$-$z$ path in the underlying graph. If the two shortcuts of $u$ are in $ℱ$, the only $s$-$z$ path in the gadget has three consecutive edges with time label $2$, and thus replacing a single time edge by a $\delta$-modification cannot create a strict $s$-$z$ journey. The only potential journeys that do not lie inside a vertex gadget are journeys that start in one vertex gadget, then follow a cross path to another vertex gadget, and finally reach $z$ in that vertex gadget. Consider such a journey $J$ that starts in the vertex gadget of $u$ and ends in the vertex gadget of $v$. A cross path between these two vertex gadgets exists only if $\{u,v\}\in E_H$. As $C$ is a vertex cover, at least one of $u$ and $v$ is in $C$, and therefore $ℱ$ contains the shortcuts of at least one of $u$ and $v$. If $ℱ$ contains the shortcuts of $v$, the suffix of the last four edges of $J$ has labels $1,2,2,3$, and again it is clear that replacing a single time edge by a $\delta$-modification cannot create a strict journey. If $ℱ$ contains the shortcuts of $u$, the prefix of the first four edges of $J$ has labels $1,2,1,2$, and again it is clear that replacing a single time edge by a $\delta$-modification cannot create a strict journey. Therefore, $ℱ$ is indeed a robust cutset of size at most $a$, and hence $I^{\prime }$ is a yes-instance of RTC.

$(\Rightarrow )$ Let $ℱ$ be a robust cutset of size at most $a=n+c$. As the vertex gadget of every vertex $u\in V_H$ contains a strict $s$-$z$-journey via just the vertices $u_2$ and $u_3$, it is clear that $ℱ$ must contain at least one time edge from each of the $n$ vertex gadgets. If $ℱ$ contains exactly one time edge from the vertex gadget for some vertex $u$, that time edge must be $(u_2{u}_3,2)$: It cannot be a different time edge from the vertex path, as then the journey using the two shortcuts has not been cut; it cannot be any of the two shortcuts either, as then modifying the time label of $(u_2{u}_3,2)$ to $3$ or $1$ would produce an $s$-$z$ journey via the other shortcut.

If $\{u,v\}\in E_H$, it is impossible that $ℱ$ contains only a single time edge from both the vertex gadget of $u$ and that of $v$, because then it would have to contain $(u_2{u}_3,2)$ and $(v_2{v}_3,2)$ as argued above, and thus the journey via just the vertices $u_2$, $x_{uv}$ and $v_3$ would not be cut. Thus, $ℱ$ must contain at least two time edges from one of the two vertex gadgets. If we define $C^{\prime }$ to be the set of all vertices $u\in V_H$ for which $ℱ$ contains at least two time edges of the vertex gadget for $u$, $C^{\prime }$ is therefore a vertex cover. As $|ℱ|\ge n+|C^{\prime }|$ and $|ℱ|\le a=n+c$, we have $|C^{\prime }|\le c$, and hence $I$ is a yes-instance of Vertex Cover.

This completes the proof for directed temporal graphs. For undirected temporal graphs, we can use the same construction and simply replace directed edges by undirected edges. For the underlying graph of the resulting temporal graph, the $s$-$z$ paths that lie inside one vertex gadget or follow a single cross path of the form $u_2,x_{uv},v_3$ or $v_2,x_{vu},u_3$ from one vertex gadget to another are isomorphic to those in the directed temporal graph discussed earlier. The additional $s$-$z$ paths enabled by making all edges undirected either use a cross path in reverse direction or use two or more cross paths, and one can easily check that no such path can be turned into a journey by modifying the time label of a single edge. Hence, the analysis for directed temporal graphs works also for undirected temporal graphs. $◀$

For $k=1$ and any $\delta \ge 1$, the result was proved in Theorem 8. Let $k^{\prime }>1$. Let $I=(𝒢,s,z,a,1,\delta )$ be an instance of RTC with $k=1$. We construct a new instance $I^{\prime }=({𝒢}^{\prime },s^{\prime },z,a,k^{\prime },\delta )$ of RTC with $k=k^{\prime }$ as follows: Shift all time labels of $𝒢$ by adding $2k^{\prime }$. Then add a new source node $s^{\prime }$ and $a+1$ edge-disjoint parallel paths from $s^{\prime }$ to $s$, each consisting of $2(k^{\prime }-1)$ edges. We refer to these paths as the new paths. In each of these new paths, the $i$-th edge is present in time step $2\cdot \lceil i/2\rceil$. For example, if $k^{\prime }=4$, then a new paths consist of six edges present at time $2,2,4,4,6,6$, respectively. The resulting temporal graph is ${𝒢}^{\prime }$. A cutset of size at most $a$ for $I^{\prime }$ cannot contain a time edge from each of the $a+1$ new paths, and hence can be assumed not to contain any time edge from some new path. Any of the new paths can be made a strict journey by subtracting $1$ from the time label of the $i$-th edge for all odd $i$. These are $k^{\prime }-1$ modifications, and it is not possible to turn any of the new paths into a strict journey with fewer modifications. Hence, for any subset $ℱ$ of at most $a$ time edges of $𝒢$, we have that $𝒢\setminus ℱ$ is $(1,\delta )$-safe with respect to $I$ if and only if ${𝒢}^{\prime }\setminus ℱ$ is $(k^{\prime },\delta )$-safe with respect to $I^{\prime }$. As $I^{\prime }$ can be constructed in polynomial time, RTC is also NP-hard for $k=k^{\prime }$ and $\delta$. The construction works for the directed and undirected case. $◀$

We now move to the non-strict case. The proof of the following theorem is similar to the proof of Theorem 8, but uses vertex gadgets and cross paths with the time labels illustrated in Figure 2 for $\delta =1$. (For $\delta >1$, the labels are multiplied with $\delta$.)

The proof is similar to the proof of Corollary 9, but the time label of the $i$-th edge of a new path is now set to $i+1$ if $i$ is odd and $i-1$ if $i$ is even. For example, if $k^{\prime }=4$, the time labels of a new path are $2,1,4,3,6,5$. Again, a new path can be turned into a non-strict journey with $k^{\prime }-1$ label modifications (e.g., subtracting one from the time label of the $i$-th edge for odd $i$), but not with fewer label modifications. The remainder of the argument is then the same as in the proof of Corollary 9. $◀$

We remark that the reductions in the proofs of Theorems 8 and 10 also show that all four versions of MinRTC are APX-hard, using arguments analogous to those given by Baier et al. [3].

Let $(𝒢,s,z,k,\delta )$ be the given instance of MinRTC. First, assume that $𝒢$ is a directed temporal graph and consider strict journeys. We create a time-expanded network $H=(V_H,E_H)$ of $𝒢$ that contains also edges corresponding to all possible $\delta$-modifications of time edges. Let $V$ and $ℰ$ and $L$ be the vertex set and set of time edges and lifetime of $𝒢$, respectively. Assume that the time labels of $𝒢$ lie in $[1,L]$. The vertex set $V_H$ of $H$ contains a vertex $v_t$ for every $v\in V$ and $1-\delta \le t\le L+\delta +1$. For every time edge $(uv,t)\in ℰ$, add edges $u_{t^{\prime }}{v}_{t^{\prime }+1}$ for $t-\delta \le t^{\prime }\le t+\delta$ to $E_H$. These edges have capacity $1$ and are referred to as the edges corresponding to $(uv,t)$. Note that $E_H$ may contain parallel edges. Furthermore, add to $E_H$ the edges $v_t{v}_{t+1}$ for all $v\in V$ and $1-\delta \le t\le L+\delta$. These edges have capacity $\mathrm{\infty }$. Note that every $s$-$z$ journey in a $(m,\delta )$-modification of $𝒢$ corresponds to a path from $s_{1-\delta }$ to $z_{L+\delta +1}$ in $H$ in the obvious way. Now compute a standard minimum $s_{1-\delta }$-$z_{L+\delta +1}$ cut $C$ in $H$ [1]. Let $ℱ$ be the set of time edges of $𝒢$ for which at least one corresponding edge in $H$ is included in $C$. Output $ℱ$ as the solution.

$ℱ$ is a robust cutset because any sequence of time edges of $𝒢\setminus ℱ$ that can be turned into an $s$-$z$ journey via an $(m,\delta )$-modification would imply the existence of an $s_{1-\delta }$-$z_{L+\delta +1}$ path in $H\setminus C$, a contradiction to the definition of $C$.

Let ${ℱ}^{\ast }$ be an optimal solution to MinRTC. Define $C^{\prime }$ to be the set of all edges of $H$ that correspond to a time edge in ${ℱ}^{\ast }$. Observe that $C^{\prime }$ is an $s_{1-\delta }$-$z_{L+\delta +1}$ cut in $H$ of size $(2\delta +1)|{ℱ}^{\ast }$. As $C$ is a minimum $s_{-\delta }$-$z_{L+\delta +1}$ cut in $H$, we have $|C|\le |C^{\prime }|=(2\delta +1)|{ℱ}^{\ast }|$. As $|ℱ|\le |C|$, the claimed approximation ratio follows.

If $𝒢$ is an undirected temporal graph, we change the construction of the directed graph $H$ slightly: If $(uv,t)$ is an undirected time edge, we add for every $t^{\prime }$ with $t-\delta \le t^{\prime }\le t+\delta$ the following edges with capacity $1$ to $H$: $u_{t^{\prime }}{x}_{uv{t}^{\prime }}$, $v_{t^{\prime }}{x}_{uv{t}^{\prime }}$, $x_{uv{t}^{\prime }}{y}_{uv{t}^{\prime }}$, $y_{uv{t}^{\prime }}{u}_{t^{\prime }+1}$, $y_{uv{t}^{\prime }}{v}_{t^{\prime }+1}$. Here, $x_{uv{t}^{\prime }}$ and $y_{uv{t}^{\prime }}$ are new vertices (different new vertices for every choice of $(uv,t)$ and $t^{\prime }$). Now, cutting the single edge $(x_{uv{t}^{\prime }},y_{uv{t}^{\prime }})$ corresponds to cutting the undirected $\delta$-modified time edge $(uv,t^{\prime })$, and the remainder of the argument goes through as before.

If we consider non-strict instead of strict journeys, the edges corresponding to time edges or $\delta$-modified time edges are inserted within a time layer of $H$, i.e., going from $u_t$ to $v_t$ rather than to $v_{t+1}$. The remainder of the argument stays the same. $◀$

The case $k\ge n-1$ is equivalent to the case $k=m$ because no journey uses more than $n-1$ time edges, and hence a temporal graph is $(n-1,\delta )$-safe if and only if it is $(m,\delta )$-safe. $◀$

Next, we consider the case of arbitrary $k$.

Let $(𝒢,s,z,k,\delta )$ be the given instance of MinRTC. First, consider directed temporal graphs and strict journeys. We create $k+1$ copies of the time-expanded network of $𝒢$ (constructed as in the proof of Theorem 17). Let $u_t(i)$ denote the copy of $u_t$ in the $i$-th time-expanded network. Each of the $k+1$ time-expanded networks contains only one edge for each time edge of $𝒢$: If $(uv,t)$ is a time edge, the $i$-th copy of the time-expanded network contains the edge $(u_t(i),v_{t+1}(i))$. For each $\delta$-modified time edge, add edges connecting the $i$-th copy to the $(i+1)$-th copy. More precisely, if $(uv,t)$ is a time edge and $t^{\prime }\ne t$ satisfies $t-\delta \le t^{\prime }\le t+\delta$, we add the edge $(u_{t^{\prime }}(i),v_{t^{\prime }+1}(i+1))$ for all $1\le i\le k$. Attach a new sink node $z^{\prime }$ with infinite-capacity edges $(z_{L+\delta +1}(i),z^{\prime })$ for $1\le i\le k+1$. Call the resulting graph $H$. For each time edge $(uv,t)$ of $𝒢$, there are now $k+1+2k\delta$ edges of capacity $1$ in $H$ that correspond to it: one edge in each of the $k+1$ copies of the time-expanded network, and $2\delta$ edges from each copy to the next.

Observe that $s$-$z$ journeys in a $(k,\delta )$-modification of $𝒢$ that has modified the labels of exactly $i$ time edges correspond to paths from $s_{1-\delta }(1)$ to $z^{\prime }$ via $z_{L+\delta +1}(i+1)$ in $H$, and thus every $s$-$z$ journey in a $(k,\delta )$-modification of $𝒢$ corresponds to an $s_{1-\delta }(1)$-$z^{\prime }$ path in $H$.

Now compute a standard minimum $s_{1-\delta }(1)$-$z^{\prime }$ cut $C$ in $H$ [1]. Let $ℱ$ be the set of time edges of $𝒢$ for which at least one corresponding edge in $H$ is included in $C$. Output $ℱ$ as the solution.

$ℱ$ is a robust cutset because any sequence of time edges of $𝒢\setminus ℱ$ that can be turned into an $s$-$z$ journey via a $(k,\delta )$-modification would imply the existence of an $s_{1-\delta }(1)$-$z^{\prime }$ path in $H\setminus C$, a contradiction to the definition of $C$.

Let ${ℱ}^{\ast }$ be an optimal solution to MinRTC. Define $C^{\prime }$ to be the set of all edges of $H$ that correspond to a time edge in ${ℱ}^{\ast }$. Observe that $C^{\prime }$ is an $s_{1-\delta }(1)$-$z^{\prime }$ cut in $H$ of size $(k+1+2\delta k)|{ℱ}^{\ast }|$. As $C$ is a minimum $s_{1-\delta }(1)$-$z^{\prime }$ cut in $H$, we have $|C|\le |C^{\prime }|=(k+1+2\delta k)|{ℱ}^{\ast }|$. As $|ℱ|\le |C|$, the claimed approximation ratio follows.

The adaptation to undirected temporal graphs and/or non-strict paths is analogous to the proof of Theorem 17. $◀$