Spanner Enumeration for Temporal Graphs

In a seminal paper, Kempe, Kleinberg, and Kumar [24] introduced the study of spanning substructures in temporal graphs, networks that evolve over time. In such graphs, connectivity is established through temporal paths, which are paths where edge labels are strictly increasing. Unlike traditional spanning trees, these substructures do not necessarily form a tree and have been termed temporal spanners by the research community. A minimal spanner is one in which no further edges can be removed without breaking connectivity. For simplicity, all spanners discussed in this paper are assumed to be minimal unless stated otherwise. Building on prior research in graph spanners, as well as insights from broadcasting and gossip theory (see survey [23]), numerous studies have since explored temporal spanners. This includes results on (in)approximability [2], counterexamples or existence of sparse spanners [3, 16, 18], adding stretch, blackout-resilience, or underlying structure [6, 5, 14], to sharp thresholds in temporal Erdös–Rényi random graphs [17].
In this paper, we formalise a temporal graph $𝒢$ as a graph $G$ with an edge time function $\lambda$, associating to each edge of $G$ a non-empty set of discrete times (see Section 2 for full definitions). We consider the following types of connectivity for spanners:

Most related work on temporal spanners focuses on all2all spanners. However, studies also exist on temporal structures with different types of connectivity, though they are not explicitly termed “spanners”. For example, the paths resulting from the algorithms in [35] and the temporal branchings in [11] both correspond to specific cases of one2all spanners. There are also temporal spanners which are defined as subsets of time edges or labels (and so minimality is defined on time edges as well) instead of on edges. Some other works, such as [16, 17], consider the special case of so-called “simple” temporal graphs, where each edge only has one assigned time, and thus the distinction disappears. We do not consider such spanners in this paper.

In this paper we study the problem of enumerating, i.e. listing exactly once, all the temporal spanners in Definition 1 for a given temporal graph in input. In the field of enumeration algorithms, significant research has focused on efficiently enumerating structures maintaining connectivity in static graphs, as discussed later. However, no prior work has tackled the following enumeration problem, where $X$ refers to one2all, one2all2one, many2all, and all2all.

With the aim of obtaining our results on the enumeration problems, we also study the following corresponding extension problems.

Indeed, being able to solve efficiently the (Connected) Extension Problem implies being able to solve efficiently the corresponding enumeration problem [32].

In order to classify the complexity of enumeration problems, the classes we will use in this paper are the standard ones: output-polynomial time, where all output can be enumerated in time polynomial in the input and the output size; incremental polynomial time, where, for all $i$, the $i$th output can be produced in polynomial time in the input size and in the number $i$; and polynomial delay, where the delay between two consecutive outputs is polynomial in the input size. Additionally, a famous unresolved problem in the enumeration field is whether Hypergraph Dualization, or Dual for short, which asks for finding all minimal hitting sets for a given hypergraph [4], can be solved in output-polynomial time for general hypergraphs. This problem has received considerable attention in the literature, since it is known to be polynomially or quasi-polynomially equivalent with many problems in various areas [22]. When we reduce a problem from Dual, we say the problem is Dual-hard, meaning that if our problem could be solved in output-polynomial time, then Dual would also admit an algorithm running in output-polynomial time. See [34, 21] for a survey on these topics.

Enumeration problems related to connectivity for graphs are widely studied and considered important. One example of enumerating minimal subgraphs that satisfy a connectivity constraint is the minimal Steiner tree enumeration. For a restricted input, a polynomial-delay enumeration algorithm has been developed, using a polynomial-time algorithm for a corresponding extension problem as a subroutine [27]. Furthermore, similar algorithms are known to work for several variants, such as minimal directed Steiner trees, minimal terminal Steiner tree, and minimal Steiner forests [27, 29]. Besides edge connectivity, enumeration problems concerning vertex connectivity have also been studied. The problem of enumerating minimal spanning $k$-vertex-connected spanning subgraphs is known to be solvable in incremental polynomial time for fixed $k$ [8]. Additionally, it is known that vertex connectivity can make an enumeration problem significantly harder. For instance, while the minimal vertex cover enumeration is known to be solvable with polynomial delay, the problem of enumerating minimal connected vertex covers, which imposes a connectivity constraint, is known to be Dual-hard [28]. Complexity of enumeration problems related to connectivity also extends to intractable problems. For example, it is known that enumerating minimal edge sets that ensure reachability between two specified vertices in a directed graph cannot be solved in output-polynomial time unless $𝖯=\mathrm{𝖭𝖯}$ [25]. Moreover, instead of enumerating minimal sets that satisfy connectivity, enumerating minimal sets that destroy connectivity has also been addressed. In particular, it has been shown that enumerating minimal vertex sets that disconnect a graph and minimal edge sets that break the strong connectivity of a directed graph cannot be solved in output-polynomial time unless $𝖯=\mathrm{𝖭𝖯}$ [7, 10].

In this paper, we establish the results summarized in Table 1. Notably, we observe that the Extension Problem for all definitions of temporal spanners is $\mathrm{𝖭𝖯}$-complete.⁴⁴4Both Extension Problem and Connected Extension Problem are in $\mathrm{𝖭𝖯}$, as we can verify in polynomial time whether a set of edges contains $E^{\prime \prime }$ and is a temporal spanner, by checking reachability, and then checking minimality by removing one edge at a time and again checking reachability. As a consequence, we cannot directly apply the standard flashlight method [32], which is commonly used to design output-polynomial enumeration algorithms. The flashlight method systematically explores the entire solution space by partitioning it into subsets that include or exclude a given edge, proceeding recursively only after verifying whether a partial solution can be extended into a full solution. However, since the Extension Problem is intractable, this verification cannot be performed in polynomial time unless $𝖯=\mathrm{𝖭𝖯}$.

On the other hand, if we enforce connectivity in the partial solution, the problem reduces to the Connected Extension Problem. We prove that in the case of one2all spanners, this problem can be solved in polynomial time, allowing us to design a polynomial-delay flashlight method for enumeration. This parallels the case of Steiner subgraphs in static graphs [19], where the Extension Problem is $\mathrm{𝖭𝖯}$-complete, but the Connected Extension Problem is sometimes tractable, enabling an output-polynomial enumeration algorithm in these cases.

For all other definitions of temporal spanners, however, the Connected Extension Problem remains $\mathrm{𝖭𝖯}$-complete.⁵⁵5Note that the hardness of Extension Problem is a consequence of the hardness of Connected Extension Problem as it is a restriction. This is not coincidental: we show that the enumeration of one2all and one2all2one spanners is Dual-hard. Consequently, achieving an output-polynomial time algorithm for these enumeration problems would imply an output-polynomial time for Dual, which is still an open problem since several years [4, 22]. It is important to note that hardness results for both Connected Extension Problem and Enumeration for many2all are tight with respect to the number of sources, as they hold for two sources.

Finally, for all2all spanners, we prove that no output-polynomial enumeration algorithm is possible unless $𝖯=\mathrm{𝖭𝖯}$. In this case, the latter result also implies the hardness of Connected Extension Problem and Extension Problem, as solving them in polynomial time would allow us to design an output-polynomial enumeration algorithm for Enumeration.

The organization is as follows: first, in Section 2, we present our models and notation used throughout the rest of the paper; then, in Section 3, we start by studying one2all spanners and obtain our tractability results; in Section 4 and Section 5, the connectivity considered is slightly modified (to one2all2one and many2all resp.) and we observe a sudden shift as the corresponding extension problems are proven to become hard and we prove the enumeration problems to be Dual-hard; next, we consider all2all spanners in Section 6 for which we obtain that the corresponding enumeration problem cannot be solved in output-polynomial time unless $𝖯=\mathrm{𝖭𝖯}$. We conclude in Section 7 and discuss interesting directions for future work.

Due to the soft page limit, results marked with a $(\star )$ have the corresponding proofs in the Appendix. For some of these, a proof sketch is present in the main part of the paper as well.

To prove $\mathrm{𝖭𝖯}$-completeness, we reduce from SAT. Let us first describe the transformation of a $\mathrm{𝖲𝖠𝖳}$ instance into a spanner extension instance. We prove that a positive $\mathrm{𝖲𝖠𝖳}$ instance corresponds to a positive instance in the spanner extension instance ($⟹$), and vice versa ($⟸$) in the complete proof in the appendix.

For the following transformation, refer to Figure 1 as well. Let the $\mathrm{𝖲𝖠𝖳}$ instance have $n$ variables $x_i$ and $m$ clauses $C_j$. Start by constructing an (initially) empty temporal graph $𝒢$ and add vertices for each possible literal, so $v_{x_i}$ and $v_{\overline{x_i}}$ for all $x_i$. Now, for each clause $C_j$, create vertex $v_{C_j}$ and connect this vertex with an edge to each vertex corresponding to a literal of $C_j$. Add label $2$ to these edges as well. Then, add vertex $s$ and add edges $\{s,v_{\mathrm{\ell }}\}$ for each possible literal $v_{\mathrm{\ell }}$. Assign label 1 to these edges. Finally, for each $v_{x_i}$, add edge $\{v_{x_i},v_{\overline{x_i}}\}$ with label $2$, and let these edges be the set of edges $E^{\prime \prime }$ that have to be in a spanner solution. The transformation is now complete.

We note that, by construction, at least one of edges $\{s,v_{x_i}\}$ and $\{s,v_{\overline{x_i}}\}$ has to be in a solution for vertices $x_i$ and $\overline{x_i}$ to be reachable from $s$. In fact, exactly one of the two must be in a solution because if both are then a cycle in the underlying graph would be created along with forced edge $\{v_{x_i},v_{\overline{x_i}}\}\in E^{\prime \prime }$, which would contradict Proposition 2. The intuition behind our reduction is that the choice between edges $\{s,v_{x_i}\}$ and $\{s,v_{\overline{x_i}}\}$ encodes the choice of setting variable $x_i$ to true or false respectively. Note also that it is necessary for the reachability of each $v_{C_j}$ to select at least one pair of edges $\{s,v_{\mathrm{\ell }}\}$ and $\{v_{\mathrm{\ell }},v_{C_j}\}$. The correctness is provided in the full proof in the appendix. $◀$

We start by running TFS on ${𝒢}^{\prime }=𝒢[E^{\prime \prime }]$ to obtain the earliest arrival times $a_{{𝒢}^{\prime }}(v)$ from $s$ to each vertex $v\in {𝒢}^{\prime }$. Afterwards, we run TFS on temporal graph $𝒢$, but change the initialization part of the algorithm (see Algorithm 1 in the Appendix). Initialize the earliest arrival times $a(v)$ as $a_{{𝒢}^{\prime }}(v)$ for every vertex $v$ of ${𝒢}^{\prime }$, and initialize the selected edge set $S$ as $E^{\prime \prime }$. This makes it so that these arrival times are never updated throughout TFS, as only arrival times that are $+\mathrm{\infty }$ get updated. Also, $S$, the resulting one2all spanner (if one exists) uses $E^{\prime \prime }$. TFS takes time $O(m\tau )$, and thus so does the described algorithm. $◀$

As discussed before, we obtain our enumeration algorithm based on binary partition. This algorithm has polynomial delay thanks to the flashlight method using Lemma 4. For the sake of space, the proof of the following result is provided in the appendix.

For proving $\mathrm{𝖭𝖯}$-hardness, consider the same transformation as in Theorem 3, from $\mathrm{𝖲𝖠𝖳}$ (see again Figure 1). Then, for each vertex $v_z$ where $z$ is some literal or clause, add vertices $v_z^1$ and $v_z^2$ and edges $\{v_z,v_z^1\}$, $\{v_z^1,v_z^2\}$, and $\{v_z^2,s\}$, with times 3, 4, 5 resp. Add to edge set $E^{\prime \prime }$ (which already contains edges $\{v_{x_i},v_{\overline{x_i}}\}$ for all variables $x_i$) these newly created edges. Note that $E^{\prime \prime }$ is connected. The transformation is now complete.

Since all edges $\{v_z,v_z^1\}$, $\{v_z^1,v_z^2\}$, and $\{v_z^2,s\}$ are in $E^{\prime \prime }$, and they allow vertices $v_z$ to reach $s$, and they do not allow $s$ to reach vertices $v_z$ (nor aid in the reachability between these vertices that could indirectly help $s$ to reach them), essentially what remains to decide in this reduction is how to connect $s$ to the other vertices. This is exactly the problem in Theorem 3, and we use the exact same structure for this (ignoring the new edges we added as we just argued they are not useful for the reachability of $s$). Hence we conclude that the result from the reduction in Theorem 3, being $\mathrm{𝖭𝖯}$-hardness, transfers for one2all2one Connected Extension Problem. $◀$

We reduce Hypergraph Dualization, or Dual, to our problem. Let us first describe the transformation of a Dual instance into a one2all2one spanner enumeration instance. Then, it is possible to prove that each minimal transversal in the Dual instance corresponds to a one2all2one spanner in the one2all2one spanner enumeration instance, and vice versa. This is proven in the appendix for space constraints.

For the following transformation, refer to Figure 2 as well. Let the Dual instance $G$ be composed of $n$ vertices $u_i$ and $m$ hyperedges $h_j$. Start by constructing an initially empty temporal graph $𝒢$ and add vertex $v_{u_i}$ for each vertex $u_i\in G$, and vertex $v_{h_j}$ for each hyperedge $h_j\in G$. For all $i,j$, if $u_i\in h_j$, then create a vertex $v_{u_i,h_j}$ in $𝒢$ and edges $\{v_{u_i},v_{u_i,h_j}\}$ and $\{v_{u_i,h_j},v_{h_j}\}$ with times $\{3,4\}$ and $\{1,4\}$ resp. Add vertex $s$ to $𝒢$. For each $v_{u_i}$, add vertices $v_{u_i}^0$, $v_{u_i}^1$, and $v_{u_i}^2$, and edges $\{s,v_{u_i}^0\}$, $\{v_{u_i}^0,v_{u_i}\}$ with times 1 and 2 resp. as well as edges $\{s,v_{u_i}^1\}$, $\{v_{u_i}^1,v_{u_i}^2\}$, and $\{v_{u_i}^2,v_{u_i}\}$ with times $\{1,3\}$, 2, and $\{1,3\}$ resp. Finally, add vertex $t$ and edges $\{v_{h_j},t\}$ with time 2 for all $h_j$, and edge $\{t,s\}$ with time 3. The transformation is now complete.

By construction, we obtain that all edges except for edges $\{v_{u_i}^0,v_{u_i}\}$ are necessary, i.e. that they are part of any one2all2one spanner of $𝒢$ w.r.t. source vertex $s$. Indeed, we have that: (i) Each edge $\{s,v_{u_i}^0\}$ is necessary for $s$ to reach vertex $v_{u_i}^0$; (ii) Each edge $\{s,v_{u_i}^1\}$ is necessary for vertex $v_{u_i}$ to reach $s$; (iii) And likewise for each edge $\{v_{u_i}^1,v_{u_i}^2\}$ and each edge $\{v_{u_i}^2,v_{u_i}\}$; (iv) Each edge $\{v_{u_i},v_{u_i,h_j}\}$ is necessary for $s$ to reach vertex $v_{u_i,h_j}$; (v) Each edge $\{v_{u_i,h_j},v_{h_j}\}$ is necessary for vertex $v_{u_i,h_j}$ to reach $s$; (vi) Each edge $\{v_{h_j},t\}$ is necessary for vertex $v_{h_j}$ to reach $s$; (vii) And finally, edge $\{t,s\}$ is necessary for $t$ to reach $s$.

Let ${𝒢}^{\prime }$ denote the temporal graph composed of these edges, i.e. ${𝒢}^{\prime }=𝒢\setminus \{v_{u_i}^0,v_{u_i}\}$, for all $u_i$ (in Figure 2, this corresponds to the illustrated temporal graph without the dashed edges). We have that in ${𝒢}^{\prime }$, all vertices can be reached by $s$ as well as reach $s$, except for vertices $v_{h_j}$, as these can only reach $s$ but not be reached by $s$. Note that adding some edge $\{v_{u_i}^0,v_{u_i}\}$ to ${𝒢}^{\prime }$ will allow $s$ to reach exactly vertices $v_{h_j}$ such that $u_i\in h_j$. We thus observe that any spanner of $𝒢$ is composed of ${𝒢}^{\prime }$ with some minimal selection of edges $\{v_{u_i}^0,v_{u_i}\}$. Correctness is provided in the complete proof in the appendix. $◀$

To prove $\mathrm{𝖭𝖯}$-completeness for Another all2all Spanner, we reduce from $\mathrm{𝖲𝖠𝖳}$. Let us first present how to construct temporal graph $𝒢$ for the Another all2all Spanner instance from a given $\mathrm{𝖲𝖠𝖳}$ instance $\varphi$, and analyze the specific structure it admits in Lemma 10.

For the following transformation, refer to Figure 3 as well. Let the $\mathrm{𝖲𝖠𝖳}$ instance be CNF formula $\varphi$ on $n$ variables $x_i$ and $m$ clauses $C_j$. Start by creating the (initially empty) temporal graph $𝒢$ and add vertices for each possible variable, so $v_{x_i}$ for all $x_i$. Now, for each clause $C_j$, create vertices $v_{C_j}$ and $v_{C_j^{\prime }}$. Add vertex $v_y$ and vertex $v_{y^{\prime }}$ as well. Now add edges from $v_y$ to all vertices $v_{C_j}$ with times $\{1,4\}$, and add edges from $v_{y^{\prime }}$ to all vertices $v_{C_j^{\prime }}$ with times $\{1,6\}$. Create vertex $v_z$ and connect it to all vertices $v_{C_j}$ with times $\{3,4\}$, to all vertices $v_{x_i}$ with times $\{1,6\}$, and to all vertices $v_{C_j^{\prime }}$ with times $\{1,2\}$. (The transformation now corresponds to the black edges in Figure 3(a) and Figure 3(b). We will now add the other vertices, and the orange and red edges.) For all ordered pairs $(v_{C_i},v_{C_j^{\prime }})$ such that $i\ne j$, create vertex $v_{C_{i,j}}$ and connect it to vertex $v_{C_i}$ with time 2, and to $v_{C_j^{\prime }}$ with time 4. For all pairs of vertices $(v_{C_{i,j}},v_{C_{h,k}})$, if $j=k$, connect them with an edge with times $\{1,4\}$; and if $i=k$ and $j=h$ (i.e. $v_{C_{h,k}}=v_{C_{j,i}}$) connect them with an edge with times $\{2,4\}$. We will use ${𝒢}^{\prime }$ to refer to the temporal subgraph of $𝒢$ containing only the edges created until now. (The construction at this point now corresponds to Figure 3(b).) We finish the construction of $𝒢$ by adding the following final edges. For all $i,j$, if literal $x_i\in C_j$, connect $v_{x_i}$ to $v_{C_j}$ with an edge, and if ${\overline{x}}_i\in C_j$, connect $v_{x_i}$ to $v_{C_j^{\prime }}$. Assign time 4 to these edges. Connect vertex $v_y$ with an edge of time 3 to each vertex $v_{x_i}$. Similarly, connect vertex $v_{y^{\prime }}$ with an edge of time 5 to each vertex $v_{x_i}$. This concludes the construction of the temporal graph $𝒢$. Let ${𝒢}^{\prime \prime }$ be the temporal graph $𝒢$ without ${𝒢}^{\prime }$, i.e. the temporal graph containing only the final edges added (or the temporal graph corresponding to Figure 3(c)).

For the following result, note that Another all2all Spanner is in $\mathrm{𝖭𝖯}$ because one can verify a solution spanner in polynomial time, by checking if it is contained in $S$, checking reachability, and then checking minimality by removing one edge at a time and again checking reachability.

As mentioned before, to prove $\mathrm{𝖭𝖯}$-hardness, we reduce $\mathrm{𝖲𝖠𝖳}$ to our problem. Let the polynomial transformation of a $\mathrm{𝖲𝖠𝖳}$ instance into a Another all2all Spanner instance be as described beforehand to obtain temporal graph $𝒢$, and let $S$ contain all the spanners described in the spanner property of Lemma 10, so for each $1\le i\le n$, add to $S$ spanner $s_i$ composed of ${𝒢}^{\prime }$ with added edges $\{v_y,v_{x_i}\}$ and $\{v_{x_i},v_{y^{\prime }}\}$. Note that now $|S|=k=n$. The transformation is now complete. We finish by proving that a positive $\mathrm{𝖲𝖠𝖳}$ instance implies a positive Another all2all Spanner instance ($⟹$), and vice versa ($⟸$).

$\mathrm{𝖲𝖠𝖳}⟹$ Another all2all Spanner:
Suppose a solution assignment $a$ for the $\mathrm{𝖲𝖠𝖳}$ instance. We construct a spanner $s$ such that $s\notin S$ as follows. By the spanner property in Lemma 10, $s$ must contain all edges of ${𝒢}^{\prime }$. For each clause $C_j$, some literal must be true in $a$. Consider one of these literals. If it is a positive variable, so $x_i$, then add to $s$ edges $\{v_{C_j},v_{x_i}\}$ and $\{v_{x_i},v_{y^{\prime }}\}$ (unless already in $s$). These edges are now necessary for $v_{C_j}$ to reach $v_{C_j^{\prime }}$. After doing this for all clauses, we claim $s$ is indeed a spanner: all edges in $s$ are necessary, so $s$ is minimal, and all vertices can reach each other (all vertices could already reach each other before going over the clauses, except for $v_{C_j}$ to $v_{C_j^{\prime }}$, which can reach through the added edges afterwards). We note that $s\notin S$ since by construction no spanner in $S$ uses any edge $\{v_{C_j},v_{x_i}\}$ or $\{v_{x_i},v_{C_j^{\prime }}\}$, for any $i,j$.

$\mathrm{𝖲𝖠𝖳}⟸$ Another all2all Spanner:
Suppose a solution all2all spanner $s$ for the Another all2all Spanner instance. Again by the spanner property of Lemma 10, we know it must contain all edges from ${𝒢}^{\prime }$. Also, it cannot contain both edges $\{v_y,v_{x_i}\}$ and $\{v_{x_i},v_{y^{\prime }}\}$ for some $i$, because that would mean $s_i\in S$ is a subgraph of $s$, and thus $s$ is not minimal (if a proper subgraph) or already in $S$ (if equal to $s_i$). Thus, $s$ must have at most one of the edges $\{v_y,v_{x_i}\}$ and $\{v_{x_i},v_{y^{\prime }}\}$ for all $i$. We construct a solution for $\mathrm{𝖲𝖠𝖳}$ in the following manner: for all $i$, if $\{v_y,v_{x_i}\}\in s$, assign $x_i$ to be false, and if $\{v_{x_i},v_{y^{\prime }}\}\in s$, then assign $x_i$ to be true. If neither edge is in $s$, then assign $x_i$ an arbitrary value, say true. We now claim this assignment evaluates $\varphi$ to true. It should be clear that no $x_i$ is assigned both true and false. For each clause $C_j$, there must be some path from $v_{C_j}$ to $v_{C_j^{\prime }}$, which must pass either through some edge $\{v_y,v_{x_i}\}$ or through some edge $\{v_{x_i},v_{y^{\prime }}\}$. In the first case, the other edge of the temporal path is $\{v_{x_i},v_{C_j^{\prime }}\}$ which by construction implies ${\overline{x}}_i\in C_j$, and since $\{v_y,v_{x_i}\}\in s$, $x_i$ is assigned false, and so clause $C_j$ evaluates to true. Similarly, in the second case, the other edge of the temporal path is $\{v_{C_j},v_{x_i}\}$ which by construction implies $x_i\in C_j$, and since $\{v_{x_i},v_{y^{\prime }}\}\in s$, $x_i$ is assigned true, and so clause $C_j$ evaluates to true. $◀$

Now, to obtain the main result of this section, we use the following folklore reasoning from the area of enumeration algorithms [31, 12, 26, 10, 9]. Suppose by contradiction that all2all Spanner Enumeration can be done in output-polynomial time, say through algorithm $A$ running in time at most ${(|𝒢|N)}^c$, for an input temporal graph $𝒢$, with $N$ the number of solutions, and some constant $c$. Now, consider an instance of Another all2all Spanner, composed of temporal graph $𝒢$ and a set of spanners $S$ such that $|S|=k=O(𝒢)$. Run algorithm $A$ on $𝒢$ for ${(|𝒢|k)}^c$ steps. Since $k=O(|𝒢|)$, we run $A$ for polynomial time. Now, if the algorithm terminates and enumerated only the spanners from $S$, then that implies the Another all2all Spanner instance is negative. Otherwise, if the algorithm does not terminate in this time or has enumerated a spanner not in $S$, it implies that the instance is positive. Thus, Another all2all Spanner could be solved in polynomial time, which, unless $𝖯=\mathrm{𝖭𝖯}$, is our contradiction because Lemma 11 proves it is $\mathrm{𝖭𝖯}$-complete.