Realization of Temporally Connected Graphs Based on Degree Sequences

Before stating the results, we recall that a degree sequence $𝐝$ is a non-increasing list of integers. A degree sequence of length $n$ is graphical if there exist an $n$-vertex (static) graph whose vertices have exactly these values as their degrees. Moreover, $𝐝$ is multigraphical if a multigraph with this degree distribution exists.

Our main result is a complete characterization of the graphical sequences that admit a realization as a simple and proper temporal graph in TC. We refer to these sequences as TC-realizable graphical sequences. The characterization, obtained in Section 5, is the following:

We also characterize the degree sequences that can be realized as a non-simple and proper temporal graph in TC, where non-simple means that a same edge can receive multiple time labels. Conveniently, non-simple temporal graphs are equivalent to simple temporal graphs whose underlying graph is a multigraph and where each edge of the multigraph only receives one label. Thus, the problem amounts to characterizing TC-realizable multigraphical sequences. The characterization is:

As one can see, both characterizations are close to each other, the set of TC-realizable multigraphical sequences being of course more general (indeed, TC-realizable graphical sequences are special cases of these). However, the difference is more important than one may think by looking only at these theorems, because multigraphical sequences already differ from graphical sequences. (Both standard characterizations will be recalled in the paper.)

On the algorithmic side, we show that TC-realizable graphical sequences can be recognized in $𝒪(n)$ time and TC-realizable multigraphical sequences in $𝒪(n+m)$ time. We also give a constructive $𝒪(n+m)$ time algorithm that outputs a temporal graph satisfying the desired constraints (if one exists), this algorithm being obviously asymptotically optimal.

The fact that we consider proper labelings is not a limitation. Precisely, if non-proper labelings are considered, then one may either consider strict (i.e. increasing) or non-strict (i.e. non-decreasing) temporal paths. In the case of strict temporal paths, we know that non-proper labelings can always be turned into proper labelings without reducing the reachability relation [7]. Together with the fact that proper labelings are particular cases of non-proper labelings, this implies that the feasible cases are the same as in the proper setting. If one considers non-strict temporal paths instead, then the problem becomes trivial to solve: a single spanning tree suffices (with the same time label on every edge). Thus, in this case, the problem reduces to testing if the sequence can be realized as a connected graph, which from earlier works [25, 23, 15] is the case if and only if $m\ge n-1$ and $d_n\ge 1$.

The characterization of TC-realizable graphs in terms of input graphs is complicated. Some necessary and sufficient conditions are known from the work of Göbel et al. [16] (itself based on earlier works in gossip theory [19, 17, 6]), the remaining cases being NP-hard to decide. A necessary condition for these graphs is to contain two spanning trees that share at most two edges. If the graphs admit two spanning trees that share at most one edge, then this is sufficient: the graph is TC-realizable. The case with two shared edges is further constrained. If the number of edges is exactly $2n-4$, then it is necessary and sufficient that the two shared edges belong to a central cycle of length $4$. Göbel et al. [16] called such graphs “$C_4$-graphs” (although they do not consist only of a cycle of length 4. To avoid this confusion, we use the term $C_4$-pivotable graphs instead. A formal definition is given in Section 2). Otherwise, there may exist feasible cases which are difficult to characterize, and these cases are precisely the ones making the problem NP-hard. Interestingly, our results imply that the framework of degree sequences allows one to circumvent these hard cases entirely.

Our characterization proceeds as follows: First, we note that the characterization of degree sequences which are realizable as a graph admitting two edge-disjoint spanning trees is known [25]. Thus, we focus on characterizing the degree sequences that can be realized as a graph admitting two spanning trees sharing exactly one edge, and, for degree sequences corresponding to exactly $2n-4$ edges, we characterize the ones admitting a realization with the above $C_4$-pivotable graph property. Surprisingly, these cases already cover all the TC-realizable graphical sequences. Namely, if a graph has strictly more than $2n-4$ edges and is TC-realizable, then its degree sequence could also be realized as a graph with two spanning trees sharing at most one edge, falling back on the previous cases. In other words, a significant by-product of our analysis is that the difficult graphs can safely be ignored in the framework of degree sequences.

In light of these explanations, the feasible cases stated in Theorem 5.1 correspond respectively to the following theorems in the paper: A degree sequence is TC-realizable if and only if it admits (i) a realization which is a $C_4$-pivotable graph (Theorem 4.1) or (ii) a realization with two spanning trees that share at most one edge (Theorem 3.1). For multigraphical sequences, we prove the characterization similarly.

All of our proofs are constructive and rely on deconstructing recursively the degree sequence to a smaller degree sequence, using gadgets that preserve two edge-disjoint spanning trees in the constructed graph (up to a central component). These constructive proofs can be implemented efficiently by using a suitable data structure that stores the degree sequence and the respective graph efficiently. The labeling is then handled separately by a dedicated procedure that achieves the claimed time using our data structure and extra features offered by the above structural algorithms.

Temporal graphs are notoriously intractable objects. Most of the results in this young field are negative and most of the problems turn out to be computationally hard, often due to the non-symmetric and non-transitive nature of reachability. In this respect, the fact the feasible cases for TC-realizability admit a characterization that is at the same time compact, purely structural, and easy to recognize appears to be significant. This situation is clearly an exception in the landscape of temporal graphs studies.

Based on this characterization, we obtain the following sufficient condition under which degree sequences with few edges are graphical.

We will make use of this corollary several times in this work to easily argue that specific degree sequences are graphical. Similarly, we also obtain the following sufficient condition.

The following algorithm constructs a graph from a graphical degree sequence.

The next lemma implies that the laying off process can be used iteratively to build a realization for a graphical degree sequence.

For multigraphical sequences there also exists a “laying off” process which is similar to Definition 2.4, but more flexible. Contrary to the graphical case, where a whole degree is laid off, in the multigraphical case, only a single edge is laid off.

The characterization of sequences admitting a realization with $k$ edge-disjoint spanning trees is identical for graphical and multigraphical sequences. For graphical sequences, it was proven constructively by Kundu for $k=2$ [25] and extended to general $k$ by Kleitman and Wang [23]. The multigraphical case was shown non-constructively by Gu, Hai, and Liang [15]. While we focus on the case $k=2$, we state the full characterization below.

Finally, we provide an overview on some known necessary and sufficient conditions of TC-realizable (multi)graphs.

This definition is equivalent to the one provided by Göbel et al. [16], since no tree can contain more than three edges of the central cycle, and due to the number of edges, each edge of the cycle is contained in at least one of the two spanning trees.

Even though it is not explicitly stated [16], the following generalization of $C_4$-pivotable graphs to multigraphs also is TC-realizable by the same labeling procedure used for $C_4$-pivotable graphs.¹¹1We will recall this labeling procedure in the full version.

Here, an induced cycle in a multigraph $G$ has the additional property that each edge of $C$ exists exactly once in $G$. Note that a $C_4$-pivotable graph is also a $C_4$-pivotable multigraph.

Now, we consider the backward direction for part (ii) of Theorem 3.1. That is, we will show the following.

First, recall Theorem 2.8, for which the following is a corollary.

Hence, it remains to consider (i) $\sum 𝐝\ge 4(n-1)-2$, $d_{n-1}\ge 2$, and $d_n=1$, and (ii) $\sum 𝐝=4(n-1)-2$ and $d_n\ge 2$. We first consider the former.

Now, we consider $\sum 𝐝=4(n-1)-2$ and $d_n\ge 2$. Note that these sequences are guaranteed to fulfill $d_n\in \{2,3\}$, as otherwise, $\sum 𝐝\ge 4n>4(n-1)-2$. We first prove the case of $d_n=3$ in Lemma 3.6, which is needed for the subsequent case $d_n=2$ in Lemma 3.8.

We will show that $n\ge 6$ in this case. To this end, we provide a lower bound on the number of entries of value $3$ in $𝐝$.

Note that this implies that , as otherwise, $𝐝$ would contain at least $n-1-4+6>n$ entries of value $3$. We distinguish between $d_2=3$ and $d_2\ge 4$.

Firstly, consider the case that $d_2=3$. Note that this implies by Claim 3.7 that $d_1=n-3$, since $\sum 𝐝=4(n-1)-2$. In other words, for each $n\ge 6$, there is exactly one degree sequence ${𝐝}^n:=(d_1^n,\mathrm{\dots },d_n^n)$ of length $n$ with $d_2^n=d_n^n=3$ fulfilling $\sum {𝐝}^n=4(n-1)-2$. Realizations with two spanning trees that share one edge for the three sequences ${𝐝}^6$, ${𝐝}^7$, and ${𝐝}^8$ are depicted in Figure 2. Now, consider $n\ge 9$. Recall that $d_1=n-3$ and $d_i=3$ for each $i\in [2,n]$. Moreover, recall that ${𝐝}^6=(3,3,3,3,3,3)$ has a realization $G^{\prime }$ with two spanning trees $T_1^{\prime }$ and $T_2^{\prime }$ that share exactly one edge (see Figure 2). Let $v_1$ be an arbitrary vertex of degree $3$ in $G^{\prime }$. We obtain a graph $G$ by adding a cycle $C$ of length $d_1-3=n-6$ to $G^{\prime }$ and adding the edge $v_{1}x$ to $G^{\prime }$ for each vertex $x$ of the cycle $C$. Note that $G$ is a realization of $𝐝$, since $G$ contains $5+d_1-3=n-1$ vertices of degree $3$ and the degree of $v_1$ was increased by $d_1-3$ to $d_1$. Since $G^c:=G[\{v_1\}\cup C]$ consists of a universal vertex attached to a cycle of length at least 3 (since $d_1-3=n-6\ge 3$ by $n\ge 9$), $G^c$ contains two edge-disjoint spanning trees $T_1^c$ and $T_2^c$. Hence, $T_1:=T_1^{\prime }\cup T_1^c$ and $T_2:=T_2^{\prime }\cup T_2^c$ are spanning trees of $G$, and $T_1$ and $T_2$ share only one edge, namely the edge shared by $T_1^{\prime }$ and $T_2^{\prime }$. Hence, $𝐝$ admits a realization with two spanning trees that share one edge.

Secondly, consider the case that $d_2\ge 4$. Note that Claim 3.7 thus implies that $n\ge d_1+4$, since $d_2\ge 4$ and $𝐝$ contains at least $d_1-4+6=d_1+2$ entries of value $3$. Let ${𝐝}^{\prime }$ be the sequence obtained from $𝐝$ by removing the entry $d_1$, removing $d_1-1$ entries of value 3, and adding a 1. We first show that ${𝐝}^{\prime }$ admits a realization with two spanning trees that share one edge, and then describe how to construct the realization for $𝐝$.

The remainder of this case is deferred to the full version. Intuitively, to then obtain a desired realization, we attach, similar to the the first case, a large cycle to a degree-$1$ vertex $v_1$. This time, the cycle has length $d_1-1$ instead of $d_1-3$ as in the first case. $◀$

Finally, we consider the case where $\sum 𝐝=4(n-1)-2$ and $d_n=2$. Essentially, we perform an induction over the length of the sequence and lay off the smallest degree $d_n=2$, until we reach a sequence of constant length or $d_n$ has value unequal to $2$. In the latter case, the previous lemma acts as a base case.

Now, we show the backward direction. That is, we show the following.

To prove this statement, we assume that we are given a graphical sequence $𝐝$ with $\sum 𝐝=4(n-1)-4$, , and $d_n\ge 2$. Note that these sequences are guaranteed to fulfill $d_n\in \{2,3\}$, as otherwise, $\sum 𝐝\ge 4n>4(n-1)-4$. We split the analysis in three cases. First, we consider the case of $d_n=3$ and $d_1\le 4$ in Lemma 4.4, then $d_n=3$ and in Lemma 4.5, and lastly $d_n=2$ and in Lemma 4.6.

Since $\sum 𝐝=4(n-1)-4$, $d_1\le 4$, and $d_n=3$, we get that $n\ge 8$, $d_{n-7}=3$, and (if $n>8$), $d_{n-8}=4$. In other words, for each $n\ge 8$, there is exactly one degree sequence ${𝐝}^n$ of length $n$ with the required properties.

We show that ${𝐝}^n$ admits a realization which is a $C_4$-pivotable graph via induction over $n$. In fact, we show a stronger result, namely, that for each $n\ge 8$, ${𝐝}^n$ has a realization $G$ which is a $C_4$-pivotable graph with central cycle $C$, such that (i) there are two spanning trees $T_1$ and $T_2$ of $G$ that share exactly two edges and both belong to $C$, and (ii) for each $i\in [1,2]$, there are two distinct edges $e_i,f_i$ from $T_i$ and outside of $C$ for which $\{e_1,e_2\}$ and $\{f_1,f_2\}$ are matchings in $G$. We call edge pairs $(e_1,e_2)$ and $(f_1,f_2)$ fulfilling these conditions matching edge pairs.

For the base case of $n=8$, consider the graph given in Figure 4 which is a realization of ${𝐝}^8=(3,3,3,3,3,3,3,3)$. As highlighted in the figure, there is a central cycle $C$ on the vertices $c_1,c_2,c_3,c_4$. Moreover, $(c_1{c}_1^{\prime },c_2{c}_2^{\prime })$ and $(c_3{c}_3^{\prime },c_4{c}_4^{\prime })$ are matching edge pairs. Hence, the statement holds for the base case of $n=8$.

Now let $n>8$ and assume that the statement holds for $n-1$. We show that the statement also holds for $n$. Let $G^{\prime }$ be a realization of ${𝐝}^{n-1}$ according to the properties of the induction hypothesis. That is, $G^{\prime }$ is a $C_4$-pivotable graph with central cycle $C$, two spanning trees $T_1^{\prime }$ and $T_2^{\prime }$ that share exactly two edges, both of which belong to $C$, and matching edge pairs $(e_1^{\prime },e_2^{\prime })$ and $(f_1^{\prime },f_2^{\prime })$. Recall that ${𝐝}^n$ can be obtained from ${𝐝}^{n-1}$ by adding a single entry of value $4$. The idea to obtain a realization for ${𝐝}^n$ with these properties is by essentially subdividing both edges $e_1^{\prime }=pq$ and $e_2^{\prime }=xy$ and identifying both newly added degree-2 vertices to obtain a new vertex $v^{\ast }$ (which then has degree 4). Formally, we obtain a graph $G$ by removing the edges $e_1^{\prime }$ and $e_2^{\prime }$ from $G^{\prime }$ and afterwards adding a new vertex $v^{\ast }$ together with the edges $p{v}^{\ast },q{v}^{\ast },x{v}^{\ast },y{v}^{\ast }$.

Note that each vertex of $V(G)\setminus \{v^{\ast }\}$ has the same degree in both $G$ and $G^{\prime }$ and $v^{\ast }$ has degree 4. Hence, $G$ is a realization of ${𝐝}^n$. Moreover, since $e_1^{\prime }$ and $e_2^{\prime }$ are not part of the central cycle $C$ of $G^{\prime }$, $C$ is still a central cycle where $T_1:=(T_1^{\prime }-e_1^{\prime })\cup \{p{v}^{\ast },q{v}^{\ast }\}$ and $T_2:=(T_2^{\prime }-e_2^{\prime })\cup \{x{v}^{\ast },y{v}^{\ast }\}$ being spanning trees of $G$ that each share exactly two edges and both of which belong to $C$. This implies that $G$ is a $C_4$-pivotable graph. It thus remains to show that there are matching edge pairs $(e_1,e_2)$ and $(f_1,f_2)$ in $G$. To define these pairs, we use the so far undiscussed pair $(f_1^{\prime },f_2^{\prime })$. Since $e_1^{\prime },e_2^{\prime },f_1^{\prime },f_2^{\prime }$ are pairwise distinct edges in $G^{\prime }$, $f_1^{\prime }$ and $f_2^{\prime }$ are still edges of $G$ and moreover, $f_1^{\prime }$ is an edge of $T_1$ and $f_2^{\prime }$ is an edge of $T_2$. Recall that $x{v}^{\ast }$ and $y{v}^{\ast }$ are edges of $T_2$, and note that $f_1^{\prime }$ contains at most one of $x$ and $y$ as an endpoint, as otherwise $f_1^{\prime }$ would be identical to $e_2^{\prime }$. Hence, there is an edge $e_2\in \{x{v}^{\ast },y{v}^{\ast }\}$ which is not adjacent to $f_1^{\prime }$, that is, $\{f_1^{\prime },e_2\}$ is a matching in $G$. With the same arguments, there is an edge $e_1\in \{p{v}^{\ast },q{v}^{\ast }\}$ which is not adjacent to $f_2^{\prime }$, that is, $\{e_1,f_2^{\prime }\}$ is a matching in $G$. This implies that $(f_1^{\prime },e_2)$ and $(e_1,f_2^{\prime })$ are matching edge pairs. Consequently, the statement holds for $n$.

Concluding, for each $n\ge 8$, the degree sequence ${𝐝}^n$ admits a $C_4$-pivotable graph realization. $◀$

Next, we consider the case that and $d_n=3$.

Essentially, we can show that the degree sequence ${𝐝}^{\prime }$ obtained by reducing $v_1$ by $2$ and removing six entries of value $3$, has a realization $G^{\prime }$ with two edge-disjoint spanning trees. To this graph, we then attach the six vertices as depicted in Figure 5 to a vertex $v_1$ of degree $d_1-2$ in $G^{\prime }$. The resulting graph is then a $C_4$-pivotable graph realization of $𝐝$. $◀$

Finally, we consider the case where and $d_n=2$. This proof is similar to the proof of Lemma 3.8. Essentially, we perform an induction over the length of the sequence and lay off the smallest degree $d_n=2$, until we reach a sequence of constant length or $d_n$ has value 3. In the latter case, one of the previous two lemmas acts as a base case.

We assume that all graphs be stored via adjacency list. Since our arguments rely on spanning trees, we assign two Boolean flags to each edge to indicate whether this edge is part of the first tree, the second tree, both, or neither of them. This will allow to extract the two spanning trees in $𝒪(n+m)$ time, once the final realization is constructed.

We now come to the additional data structure for degree sequences and (multi)graphs. Instead of storing degree sequences as sequences of numbers, we store them as double-linked list that store entries of the form $(x,c)$. Such an entry indicates that the respective degree sequence contains exactly $c$ entries of value $x$. The entries of the double-linked list are sorted decreasingly according to their $x$-values. In this way, both in the graphical and multigraphical case, we can lay off a degree $d_i$ in $𝒪(d_i)$ time, since we only need to remove $d_i$ and rearrange the $c$-values of the at most $d_i+1$ first entries of the data structure. In this data structure, we can ensure that the degree sequence always stays sorted and no reordering is necessary.

Similarly, we use an additional data structure for (multi)graphs $G$. It is also a double-linked list and stores entries of the form $(x,S)$. Such an entry indicates that the vertices of $S$ are exactly the vertices of $G$ that have degree exactly $x$. These entries are also sorted decreasingly according to their $x$-values. This way, we can reattach a vertex of degree $d_n$ to $G$ by adding edges properly to vertices of the first $d_n$ entries of the data structure. That is, we can obtain a realization for the degree sequence that, after laying off a vertex of degree $d_n$, leads to the degree sequence of $G$. In particular, this can be done in $𝒪(d_n)$ time.

In case of a realization for a $C_4$-pivotable (multi)graph, we also output the central cycle separately.

We now turn to the algorithmic aspects of finding a realization with two edge-disjoint spanning trees and show that such a realization can be computed in linear time.

For the graphical case, we used the result by Kundu [25]. While their proof is constructive in nature, the arguments are brief and incomplete. Thus, we give a complete construction in Lemma 6.1 and argue how it can be implemented in $𝒪(n+m)$ time using our data structure.

For the multigraphical case, we build on the result by Gu et al. [15], which was proven non-constructively. In Lemma 6.4, we give a complete inductive construction for such multigraphical sequences, and argue that this construction, too, can be carried out in $𝒪(n+m)$ time using our data structure.

To prove the statement, we show that for each $n$ and for each graphical sequence $𝐝$ of length $n$ with $\sum 𝐝\ge 4(n-1)$ and $d_n\ge 2$, we can construct a realization with two edge-disjoint spanning trees. We show this statement via induction over $n$.

For the base case, note that for $n\in \{1,2,3\}$, there is no graphical sequence of length $n$ that sums up to $4(n-1)$. Moreover, for $n=4$, $(3,3,3,3)$ is the only graphical sequence of length $n$ with $\sum 𝐝\ge 4(n-1)$ and $d_n\ge 2$. Since the complete graph on four vertices, which obviously contains two edge-disjoint spanning trees, is the only realization of $𝐝$, the base case holds for $n\le 4$.

For the inductive step, let $n\ge 5$ and assume that the statement holds for $n-1$. Let $𝐝$ be an arbitrary graphical sequence of length $n$ fulfilling $\sum 𝐝\ge 4(n-1)$ and $d_n\ge 2$. We show that $𝐝$ admits a realization with two edge-disjoint spanning trees. Observe that whenever $\sum 𝐝=4(n-1)$, it holds that $d_n\in \{2,3\}$ as otherwise $\sum 𝐝\ge 4n$.

If $\sum 𝐝=4(n-1)$ and $d_n=2$, or $\sum 𝐝>4(n-1)$ and $d_n\ge 2$, consider the residual sequence ${𝐝}^{\prime }=(d_1^{\prime },\mathrm{\dots },d_{n^{\prime }}^{\prime })$ of length $n^{\prime }=n-1$ obtained from laying off the entry $d_n$ according to Definition 2.4. In the full version, we show that this degree sequence fulfills the conditions of the induction hypothesis and thus admits a realization with two edge-disjoint spanning trees. Moreover, we can then obtain a desired realization for $𝐝$ by reattaching a vertex of degree $d_n$.

Otherwise, $\sum 𝐝=4(n-1)$ and $d_n=3$. In that case, consider the sequence ${𝐝}^{\prime }$ obtained from $𝐝$ by reducing $d_1$ by 1 and removing the entry $d_n$.

Now consider the graph $G$ obtained from $G^{\prime }$ by adding a degree-3 vertex $v_n$, connecting it to a vertex $v_1$ of $G^{\prime }$ of degree $d_1-1$, and inserting it on an arbitrary edge $v_i{v}_j$ of $G^{\prime }$ with $v_1\notin \{v_i,v_j\}$ (replacing $v_i{v}_j$ with $v_n{v}_i$ and $v_n{v}_j$). Then $G$ is a realization of $𝐝$. Moreover, $G$ contains the edge-disjoint spanning trees $T_1:=T_1^{\prime }\cup v_1{v}_n$ and $T_2:=(T_2^{\prime }-v_i{v}_j)\cup \{v_n{v}_i,v_n{v}_j\}$.

We defer the analysis of the running time to the full version. $◀$

For multigraphical sequences, we split the proof in two parts: we first show how to construct the desired realization for a multigraphical sequence $𝐝$ with $\sum 𝐝=4(n-1)$ and $d_n\ge 2$ in Lemma 6.3, and then describe how this can be used to obtain a realization for every multigraphical sequence fulfilling $\sum 𝐝>4(n-1)$ and $d_n\ge 2$.

Intuitively, this result is again obtained via a constructive induction over the of $n$. Two cases are distinguished in the inductive step: If $d_n=2$, then simply laying off $d_n$ and reattaching it to the provided solution for the sequence of length $n-1$ provides a desired realization. By our data structure, this laying off and reattaching can be done by a constant time overhead. If $d_n=3$, then the degree sequence actually is graphical and the algorithm behind Lemma 6.1 provides the desired result. $◀$

The construction for sequences with a degree sum larger than $4(n-1)$ follows directly from the laying-off process for multigraphical sequences (Theorem 2.7), which reduces the degree sum by two while preserving the length of the sequence.

By carefully recalling the existential proofs of the previous sections, one can observe that these proofs imply linear-time constructions by using the data structure.

We recall the labeling schemes for TC-labelings (that can be implemented in linear time) in the full version. We conclude the following algorithmic main result of our work.