Recognizing and Realizing Temporal Reachability Graphs

As mentioned, our work falls into the area of temporal graph realization problems. In these problems, one is given some data about the behavior of a temporal graph, and the goal is to detect whether there actually is a temporal graph with this behavior (and to compute such a temporal graph if one exists). Klobas et al. [17] introduced the problem of deciding for a given matrix of fastest travel durations and a period $\mathrm{\Delta }$ whether there exists a simple temporal graph $𝒢$ with period $\mathrm{\Delta }$ with the property that the duration of the fastest temporal path between any pair of nodes in $𝒢$ is equal to the value specified in the input matrix. Erlebach et al. [13] extended the problem to a multi-label version, where each edge is allowed up to $\mathrm{\ell }$ time labels. Motivated by the design of transportation networks, a related problem with respect to upper-bounded travel durations was considered [19, 20, 21].

In an early example of a temporal network design problem studied by Kempe et al. [15], the goal was to reconstruct a temporal labeling restricted to a single label per edge, so that a designated root reaches via temporal paths all vertices in a set $P$ while avoiding those in a set $N$. For multi-labeled temporal graphs, Mertzios et al. [18] studied the problem of designing a temporal graph that preserves the reachability relation or all paths of an underlying static graph while minimizing either the temporality (maximum number of labels per edge) or the temporal cost (total number of labels used). Göbel et al. [14] showed that it is NP-complete to decide whether the edges of a given undirected graph can be labeled with a single label per edge in such a way that each vertex can reach every other vertex via a strict temporal path. Notably, this problem becomes solvable in linear time when only the degree sequence of the underlying graph is given [4]. Other studies have focused on variants of minimizing edge deletions [12], vertex deletions [25], or edge delays [9] to restrict reachability, motivated, for instance, by epidemic containment strategies that limit interactions. Temporal network design is an active area of research, with further related questions explored for example in [1, 16, 7].

Casteigts et al. [3] studied the relationships between the classes of reachability graphs that arise from undirected temporal graphs if different restrictions are placed on the graph (simple, proper, happy [3]) and depending on whether strict or non-strict temporal paths are considered. They showed that reachability with respect to strict temporal paths in arbitrary temporal graphs yields the widest class of reachability graphs while reachability in happy temporal graphs yields the narrowest class. The class of reachability graphs that arise from proper temporal graphs is the same as for non-strict paths in arbitrary temporal graphs, and this class is larger than the class of reachability graphs arising from non-strict reachability in simple temporal graphs. Strict reachability in simple temporal graphs was also shown to lie between the happy case and the general strict case. Döring [11] completed the picture of a two-stranded hierarchy for undirected temporal graphs and also extended the study to directed temporal graphs. As noted earlier, Casteigts et al. [3] also posed the open question of whether there is a characterization of directed graphs that arise as reachability graphs of temporal graphs (or of some restricted subclass of temporal graphs), and how hard it is to decide whether a given directed graph is the reachability graph of some temporal graph. These questions were posed again by Döring [11]. This is in particular of interest because Casteigts et al. [6] showed that several temporal graph problems can be solved in FPT time with respect to temporal parameters defined over the reachability graph. In this paper, we resolve these open questions regarding the complexity of all directed and undirected variants.

In Section 2, we provide a formal problem definition and define the notions used in this work. In Section 3, we show upper and lower bounds for the required number of labels per edge in any realization and provide a single exponential algorithm for all problem variants. Afterwards, in Section 4, we analyze properties and define splitting operations based on bridge edges in the solid graph of the undirected versions of our problem. These structural insights will be mainly used in our FPT algorithm in Section 6, but also immediately let us describe a polynomial-time algorithm for instances where the solid graph is a tree in Section 4.2. In Section 5, we then provide NP-hardness results for all undirected problem versions as well as parameterized intractability results for two of them with respect to feedback vertex set number and treedepth. Afterwards, in Section 6, we provide our main algorithmic result: an FPT algorithm with respect to the feedback edge set number $\mathrm{fes}$ of the solid graph. This algorithm is achieved in three steps: Firstly, we apply our splitting operations of Section 4 and provide a polynomial-time reduction rule to simplify the instance at hand, such that all we need to deal with is a subset $X^{\ast }$ of vertices of size $𝒪(\mathrm{fes})$ for which the remainder of the graph decomposes into edge-disjoint trees that only interact with $X^{\ast }$ via two leaves each. We call such trees connector trees. Secondly, we show that we can efficiently extend the set $X^{\ast }$ to a set $W^{\ast }$ of size $𝒪(\mathrm{fes})$ such that each resulting connector tree for the set $W^{\ast }$ is more or less independent from the remainder of the graph with respect to the interactions of temporal paths in any realization. All these preprocessing steps run in polynomial time. Afterwards, our algorithm enumerates all reasonable labelings on the edges incident with vertices of $W^{\ast }$ and tries to extend each such labeling to a realization for $D$. As we show, there are only FPT many such reasonable labelings and for each such labeling, there are only FPT many possible extensions that need to be checked. Finally, in Section 7, we briefly discuss the directed version of the problem and provide NP-hardness results for all but the two trivial cases. Proofs of statements with $(\star )$ are deferred to the full version.

If $D_{uv}=1$ and $D_{vu}=1$ for some $u\ne v$, we say that there is a solid edge between $u$ and $v$. If $D_{uv}=1$ and $D_{vu}=0$, we say that there is a dashed arc from $u$ to $v$. We use $G=(V,E)$ to denote the graph on $V$ whose edge set is the set of solid edges, and we refer to this graph as the solid graph (of $D$). For URGR it is clear that only solid edges can receive labels in a realization of $D$, as the two endpoints of an edge that is present in at least one time step can reach each other. Bridges of the solid graph must receive labels, but a solid edge $e$ that is not a bridge may not receive labels, as the endpoints of $e$ could reach each other via temporal paths of length greater than one.

Note that for Proper URGR, Happy URGR, and all versions of Non-strict URGR, no realization for $D$ can assign labels to both of two adjacent edges $\{u,v\}$ and $\{v,w\}$ if $D$ contains neither $(u,w)$ nor $(w,u)$.

A path $P=(u_0=u,\mathrm{\dots },u_{\mathrm{\ell }}=v)$ from $u$ to $v$ in $G$ is a dense $u$-$v$-path if there exist arcs $(u_i,u_j)\in A$ for all . In each undirected realization of $D$, each temporal path is a dense path in $G$.

We say that a realization $\lambda$ is frugal if there is no edge $e$ such that the set of labels assigned to $e$ can be replaced by a smaller set while maintaining the property that $\lambda$ is a realization. We say that a realization $\lambda$ is minimal on edge $e$ if it is impossible to obtain another realization by replacing $\lambda (e)$ with a proper subset. A realization is minimal if it is minimal on every edge $e$. Note that every frugal realization is also minimal.

We reduce from Set Cover which is W[2]-hard when parameterized by $k$ [10].

Let $I:=(U,ℱ,k)$ be an instance of Set Cover with $ℱ=\{F_1,\mathrm{\dots },F_r\}$. Assume without loss of generality that each element of $U$ is contained in at least one hyperedge and that $ℱ$ has size at least $k$, as otherwise $I$ could be solved trivially. We obtain a directed graph $D=(V,A)$ with solid graph $G=(V,E)$ as follows: The graphs contain the vertices $\{\top ,a,a^{\prime },b,b^{\prime },\perp \}$, each element $u\in U$ as a vertex, and for each $i\in [1,k]$ the vertex $c_i$. Additionally, for each $F\in ℱ$ and each $u\in F$, $G$ contain the vertices $w_u^F$, $v_u^F$, and $q_u^F$.

Next, we describe the solid edges of $G$, that is, the bidirectional arcs of $D$. See Figure 2 for the solid edges and dashed arcs of the main connection gadget of the instance.

The graph $G$ contains the edges $\{a,a^{\prime }\}$, $\{b,b^{\prime }\}$, and for each $i\in [1,k]$, the edges $\{a^{\prime },c_i\}$, $\{c_i,b^{\prime }\}$, and $\{c_i,\top \}$. Moreover, for each $F\in ℱ$ and each $u\in F$, $G$ contains the edges $\{u,w_u^F\}$, $\{w_u^F,a\}$, $\{w_u^F,b\}$, $\{\{w_u^F,c_i\}\mid i\in [1,k]\}$, $\{w_u^F,v_u^F\}$, $\{w_u^F,q_u^F\}$, $\{v_u^F,\perp \}$, and $\{q_u^F,\top \}$.

Finally, we describe the dashed arcs: $D$ contains the dashed arcs $(a^{\prime },b)$, $(b,a)$, $(a^{\prime },\top )$, $(b,\top )$, and $(\top ,b^{\prime })$. For each $i\in [1,k]$, $D$ also contains the dashed arcs $(b,c_i)$ and $(c_i,a)$. Let $u\in U$. Then, $D$ contains the arc $(u,\top )$. Moreover, $D$ contains the arcs $(u,a)$, $(u,b)$, $(u,b^{\prime })$, and $(u,c_i)$ for each $i\in [1,k]$. Additionally, for each hyperedge $F\in ℱ$ with $u\in F$, $D$ contains the arcs $(u,v_u^F)$, $(v_u^F,a)$, $(b,v_u^F)$, $(w_u^F,\top )$, $(w_u^F,b^{\prime })$, $(a^{\prime },w_u^F)$, $(q_u^F,v_u^F)$, $(q_u^F,a)$, $(q_u^F,b)$, $(q_u^F,b^{\prime })$, and $(q_u^F,c_i)$ for each $i\in [1,k]$. The only other dashed arcs in $D$ are between $v_u^F$-vertices. Let $F_x,F_y\in ℱ$ with and let $u_x\in F_x$ and $u_y\in F_y$. Then, $D$ contains the arc $(v_{u_x}^{F_x},v_{u_y}^{F_y})$.

This completes the construction of $D$. First, we show the parameter bounds.

We show that $I$ is a yes-instance of Set Cover if and only if $D$ is realizable via strict temporal paths. More precisely, we show that if $I$ is a yes-instance of Set Cover, then there is a simple undirected temporal graph with strict reachability graph $D$. This then implies the correctness of the reduction for both Any Strict URGR and Simple Strict URGR.

We defer this proof to the full version and only provide an informal idea for the correctness. Intuitively, in each realization for $D$, for each $i\in [1,k]$, there can be at most one hyperedge $F\in ℱ$ for which edges between $c_i$ and vertices of $W_F:=\{w_u^F\mid u\in F\}$ can receive labels. This can be seen as follows: For each $w_{u^{\prime }}^{F^{\prime }}\in V$, (i) there is no dashed arc between $w_{u^{\prime }}^{F^{\prime }}$ and $\perp$ and (ii) there is no dashed arc between $v_{u^{\prime }}^{F^{\prime }}$ and $c_i$. Hence, Observation 1 implies that, if $\{w_{u^{\prime }}^{F^{\prime }},c_i\}$ receives at least one label, then there is some ${\alpha }_{F^{\prime }}\in \mathbb{N}$, such that the edges $\{w_{u^{\prime }}^{F^{\prime }},c_i\}$ and $\{v_{u^{\prime }}^{F^{\prime }},\perp \}$ receive the label set $\{{\alpha }_{F^{\prime }}\}$ under $\lambda$. Based on the dashed arcs between the $v_{u^{\prime }}^{F^{\prime }}$-vertices, the label ${\alpha }_{F^{\prime }}$ and the label ${\alpha }_{F^{\prime \prime }}$ are distinct for distinct hyperedges $F^{\prime }$ and $F^{\prime \prime }$. This then implies that there can be at most one hyperedge $F\in ℱ$ for which edges between $c_i$ and vertices of $W_F$ can receive labels, as otherwise, a strict temporal path between distinct $w_{u^{\prime }}^{F^{\prime }}$-vertices would be realized.

The edges with at least one label between $c_i$ and $w_u^F$-vertices thus resemble a selection of at most one hyperedge of $ℱ$ for each $i\in [1,k]$. Since the only dense paths from a vertex $u\in U$ to $\top$ are of the form $(u,w_u^F,c_i,\top )$ for $i\in [1,k]$ and $F\in ℱ$ with $u\in F$, this selection of $k$ hyperedges encodes a set cover, as the arcs $(u,\top )$ are realized over such dense paths. $◀$

Let $G=(V,E)$ be the solid graph and let $F$ be a minimum size feedback edge set of $G$. We assume without loss of generality that $G$ is connected, as otherwise, we can solve each connected component independently, or detect in polynomial time that $D$ is not realizable if there are dashed arcs between different connected components of the solid graph. Moreover, let $X$ denote the endpoints of the edges of $F$. Note that $|X|\le 2\cdot |F|$. We define the set $V^{\ast }$ as the (unique) largest subset $S$ of vertices of $V$ that each have at least two neighbors in $G[S]$, that is, $V^{\ast }$ is the 2-core [24] of $G$. This set can be computed in polynomial time. Moreover, we define $V^{\prime }:=V\setminus V^{\ast }$. Note that $X\subseteq V^{\ast }$, since $F$ is a minimum-size feedback edge set. Since $G$ is connected, for each vertex $v^{\prime }\in V^{\prime }$, there is a unique vertex $v\in V^{\ast }$ which has closest distance to $v^{\prime }$ among all vertices of $V^{\ast }$. For a vertex $v\in V^{\ast }$, denote by $V_v$ the set of all vertices of $V^{\prime }$ for which $v$ is the closest neighbor in $V^{\ast }$. Note that $V_v$ might be empty. Since $v^{\prime }$ is in no cycle, removing $v$ from $G$ would result in $v^{\prime }$ ending up in a component that has no vertex of $V^{\ast }$. Hence, $T_v:=G[\{v\}\cup V_v]$ is a tree for which we call $v$ the root. Moreover, we call $T_v$ the pendant tree of $v$.

Recall that each vertex of $V^{\ast }$ has degree at least $2$ in $G[V^{\ast }]$. Furthermore, $G-F$ is acyclic and thus $G[V^{\ast }]-F$ is a tree. Let $Y_3$ denote the set of all vertices of degree at least $3$ in $G[V^{\ast }]-F$, and let $Y_2$ be the neighbors of $X\cup Y_3$ in $V^{\ast }\setminus (X\cup Y_3)$. Observe that each leaf of $G[V^{\ast }]-F$ is a vertex of $X$. Moreover, in each tree with $\mathrm{\ell }$ leaves, there are $𝒪(\mathrm{\ell })$ vertices having (i) degree at least 3 or (ii) a neighbor of degree at least 3. This implies that $|Y_2\cup Y_3|\in 𝒪(|X|)$. Let $X^{\ast }:=X\cup Y_2\cup Y_3$. See Figure 3 for an illustration of these sets of vertices and some of the main definitions used in this section. By the above, $|X^{\ast }|\in 𝒪(|X|)\subseteq 𝒪(\mathrm{fes})$. Recall that each vertex of $Y_2$ has degree exactly $2$ in $G[V^{\ast }]$. Moreover, note that each vertex of $V^{\ast }\setminus X^{\ast }$ is part of a unique path $P$ where each internal vertex of $P$ is from $V^{\ast }\setminus X^{\ast }$ and the endpoints of $P$ are from $Y_2$. For each such path, each internal vertex has degree exactly $2$ in $G[V^{\ast }]$ and there are at most $|X^{\ast }|-1$ such paths, since $G[V^{\ast }]-F$ is acyclic. Note that $X^{\ast }$ contains all vertices that are part of triangles in $G[V^{\ast }]$ and thus in $G$. This implies that in each minimal realization of $D$, each edge incident with at least one vertex of $V\setminus X^{\ast }$ receives at most two labels (see Lemma 2). We now define the above mentioned paths between the vertices of $Y_2$ is a more general way.

Note that the endpoints of each $X^{\ast }$-connector are from $Y_2$ and thus have degree $2$ in $G[V^{\ast }]$. Moreover, each internal vertex $v$ of a $W$-connector $P$ has degree exactly $2$ in $G[V^{\ast }]$, that is, the only two neighbors of $v$ in $G[V^{\ast }]$ are the predecessor and the successor of $v$ in $P$. This also implies that each endpoint of a $W$-connector has degree exactly 2 in $G[V^{\ast }]$. Since each edge of $P$ is incident with at least one vertex of $V\setminus W\subseteq V\setminus X^{\ast }$, in each minimal realization of $D$, each edge of each $W$-connector receives at most two labels (see Lemma 2). The latter also holds for each $W$-connector tree.

Note that this is a general property of graphs with a feedback edge set of size $\mathrm{fes}$.

Our algorithm uses two preprocessing steps.

In the first step, we will present a polynomial-time reduction rule based on the splitting operations presented in Section 4. With this reduction rule, we will be able to remove vertices from large pendant trees. After exhaustive application, for each vertex $x\in V^{\ast }$, the pendant tree $T_x$ will have $𝒪(d_x)$ vertices, where $d_x$ denotes the degree of $x$ in $G[V^{\ast }]$.

In the second step, we extend the set $X^{\ast }$ to a set $W^{\ast }\subseteq V^{\ast }$ such that each $W^{\ast }$-connector has some useful properties (we will define connectors with these properties as nice connectors). Intuitively, a connector $P$ with extension $C$ is nice if (i) in a realization for $D$, the arcs in $D[V(C)]$ can only be realized by temporal paths that are contained in the connector tree $C$, and (ii) for each arc between a vertex outside of $C$ and a vertex inside of $C$, we can in polynomial time detect over which (unique) edge of the connector incident with one of its endpoints this arc is realized. As we will show, we can compute such a set $W^{\ast }$ of size $𝒪(\mathrm{fes})$ in polynomial time, or correctly detect that the input graph is not realizable. By the first part, we additionally get that the total number of vertices in pendant trees that have their root in $W^{\ast }$ is $𝒪(|W^{\ast }|+\mathrm{fes})=𝒪(\mathrm{fes})$.

The algorithm then works as follows: We iterate over all possible partial labelings $\lambda$ on the $𝒪(\mathrm{fes})$ edges incident with vertices of $W^{\ast }$ or vertices of pendant trees that have their root in $W^{\ast }$. As we will show, we can assume that each of these edges will only receive $𝒪(\mathrm{fes})$ labels in each minimal realization. For each such labeling $\lambda$, we need to check whether we can extend the labeling to the so far unlabeled edges, that is, the edges that are part of any $W^{\ast }$-connector tree. As we will show, we can compute for each such connector $P$ with extension $C$ in polynomial time a set $L_P$ of $𝒪(1)$ labelings for the edges of $C$, such that if $\lambda$ can be extended to a realization for $D$, then we can extend $\lambda$ (independently from the other connectors) by one of the labelings in $L_P$. Since $W^{\ast }$ has size $𝒪(\mathrm{fes})$, there are only $𝒪(\mathrm{fes})$ many $W^{\ast }$-connectors (see Observation 19) and for each such connector $P$, the set $L_P$ of labelings has constant size. Our algorithm thus iterates over all possible $𝒪{(1)}^{𝒪(\mathrm{fes})}=2^{𝒪(\mathrm{fes})}$ labeling combinations for the connectors and checks whether one of these combinations extends $\lambda$ to a realization for $D$. Summarizing, we will show the following.

The running time of this algorithm is then ${\mathrm{fes}}^{𝒪({\mathrm{fes}}^2)}\cdot n^{𝒪(1)}$, since (i) all preprocessing steps run in polynomial time, (ii) we only have to consider ${\mathrm{fes}}^{𝒪({\mathrm{fes}}^2)}$ labelings $\lambda$ (since we prelabel $𝒪(\mathrm{fes})$ edges with $𝒪(\mathrm{fes})$ labels each), and (iii) for each labeling $\lambda$, we only have to check for $2^{𝒪(\mathrm{fes})}$ possible ways to extend $\lambda$ to a realization for $D$. To see the second part, we show that it is sufficient to assign only labels of $\{i\cdot 2\cdot n\mid i\in 𝒪({\mathrm{fes}}^2)\}$ in $\lambda$.