Dismountability in Temporal Cliques Revisited

The above negative results immediately prompt the question of whether some restricted classes of temporal graphs admit sparse spanners unconditionally. In [13], Casteigts, Peters, and Schoeters showed that if the footprint is a complete graph (the input is a temporal clique), then $O(n\log n)$-sparse spanners are guaranteed, whatever the labeling. Quite naturally, the hardest cases are when every edge has a single label and adjacent labels are all different, i.e. the labeling is both simple and proper, respectively. Indeed, using more labels can only increase reachability, and so does having two adjacent edges with the same label, as the times along temporal paths must only be non-decreasing. (If one requires strict temporal paths, non-proper labelings may be worse, but this case is less interesting, as it allows arbitrary graphs to be unsparsifiable by simply having the same label on every edge [1, 18].)

Thus, in the context of temporal spanners (and in the present paper), a temporal clique refers to a temporal graph $𝒢=(V,E,\lambda )$ where $(V,E)$ is a complete graph and $\lambda :E\to \mathbb{N}$ is single-valued and locally injective (i.e., simple and proper). If one prefers, one may think of it as having globally unique labels, without consequences for the spanner problem. Temporal bicliques are defined analoguously, except that the footprint is a complete bipartite graph.

The $O(n\log n)$ result in [13] was obtained by a combination of techniques. The first half of the proof involves dismountability and an algorithm called fireworks, which reduces the general problem to the particular case of finding a spanner in a temporal complete bipartite graph with significant extra structure. The second part of the proof shows that such graphs admit $O(n\log n)$ spanners using a technique called iterative delegation. In a recent article, Angrick et al. [3] show that the bipartite version of the problem not only captures the hard instances; it is actually equivalent to the original problem in the sense that the worst-case size of a spanner in cliques and such bicliques are related by a constant factor. They also show that the second part of the proof involving bicliques can be simplified by using a one-sided version of dismountability in place of iterative delegation, breaking the problem into two sub-problems recursively and recovering the $O(n\log n)$ result more simply.

As of today, the status of the problem is unsettled. In particular, it remains open whether temporal cliques always admit $O(n)$ spanners. Some sub-families of cliques do, for example cliques that are pivotable or recursively dismountable [13] (more on this later), cliques resulting from encounters of agents moving along the line [17], cliques whose labeling is random [14], and cliques whose labeling obeys various technical restrictions [3].

In this paper, we revisit methodically the dismountability principle. In its default version, $1$-hop dismountability, this principle says that if a node $v$ is both the latest neighbor of some node and the earliest neighbor of another node, then $v$ can be removed from the instance at the cost of including two edges in the spanner, and one can subsequently recurse on $𝒢\setminus \{v\}$. This technique can be generalized to $k$-hop dismountability, when a similar relation applies between $v$ and other nodes through temporal paths of length at most $k$. In this case, the number of edges added to the spanner before recursion is at most $2k$, which implies that minimal counter-examples to the existence of $2kn$ spanners cannot be $k$-hop dismountable.

We start by characterizing the structure of temporal cliques which are non $1$-hop dismountable, then neither $1$-hop nor $2$-hop dismountable (i.e., non $\{1,2\}$-hop dismountable), and finally non $\{1,2,3\}$-hop dismountable. This structure is characterized in a necessary and sufficient way. Quite surprisingly, we show that if a clique is $k$-hop dismountable for $k>3$, then it must also be $k$-hop dismountable for some $k\le 3$, which implies that one does not need to analyse the structure of non $k$-hop dismountability beyond this point. For technical reasons, our analysis actually implies that any counter example to the existence of $4n$ (not just $6n$) spanners must possess all the characterized properties.

If one is interested only in the existence of $O(n)$ spanners (regardless of the constant), then it turns out that excluding only $1$-hop and $2$-hop dismountability is already sufficient for reducing the spanner problem from cliques to extremally matched bicliques, while preserving the same number of vertices, thus replacing more simply the fireworks algorithm from [13]. As a result, the entire $O(n\log n)$ result can now be recovered using dismountability only, with a simple and unified constructive algorithm.

In the second part of the paper, we further explore the properties of (non-)dismountability, some of its possible relaxations and its connections to other techniques, including pivotability. In particular, we show that if a temporal clique is recursively $k$-hop dismountable, then it is also pivotable. We also define the concept of a (time-)compressed temporal graph and identify a new family of labelings called full-range, which corresponds to compressed temporal graphs whose lifetime (interval of existence) is equal to the number of edges. We prove that full-range cliques are $\{1,2,3\}$-hop dismountable, and full-range temporal graphs in TC (not necessarily cliques, but including all temporal cliques) are pivotable. These results give some evidence that having a large lifetime could be helpful for the construction of spanners.

Beyond structural results, temporal spanners have attracted significant attention over the last decade. On the algorithmic side, the problem of minimizing the number of labels of a temporal spanner was shown APX-hard in the “non-simple, non-proper, strict” setting [1] and in the “simple, non-proper, non-strict” setting [4], both settings being incomparable in terms of expressivity [12]. Observe that in the second setting, the problem coincides with that of minimizing the number of edges (as the graph is simple), so this version of the problem is APX-hard as well. The status of the problem is open for general temporal graphs which are both simple and proper. Finally, deciding if a given temporal graph admits a temporal spanning tree is NP-complete in the “non-simple, proper” setting (regardless of whether strict or non-strict paths are considered) [11].

Observe that most of these works are only concerned with the size of the spanners, which contrasts with typical spanner problems in static graphs, where solutions of size $n-1$ (spanning trees) are de facto guaranteed and further criteria are thus considered (typically, weights and tradeoffs between density and stretch factors, see e.g. [16, 15, 5, 2]). The reader interested additional criteria in a temporal setting is referred to [6] (stretch factors), [7] (fault-tolerance), and [9] (timing criteria).

On the structural side, a few other related results were obtained. In [14], Casteigts, Raskin, Renken, and Zamaraev show that any counter-example family to linear-size spanners (such as the graphs from [18] and in [4]) are statistically insignificant. Namely, temporal Erdös-Rényi graphs almost surely admit spanners of size $2n+o(n)$ as soon as they become temporally connected (at $p=(3+ϵ)\log n/n$). Interestingly, results from the 80-90s in gossip theory can be re-interpreted in the framework of temporal graphs, shedding light on the structure of minimal temporal graphs in TC. For example, the characterization of minimal information flows in [19] implies a similar quadratic bound as the infinite family from [4], once interpreted in the setting of temporal graphs.

Finally, some recent work in network creation games directly exploit the existence of $O(n\log n)$-sparse spanners in temporal cliques [8], in a game-theoretic context.

The document is organized as follows. In Section 2, we recall the basic definitions of $1$-hop and $k$-hop dismountability. In Section 3, we characterize the structure of non $k$-hop dismountable graphs for $k\le 3$ and we show that considering larger values of $k$ is unnecessary. In Section 4, we summarize the overall proof of existence of $O(n\log n)$ spanner in temporal cliques, using only dismountability arguments. In Section 5, we provide further results about dismountability, pivotability, and full-range temporal graphs. We conclude in Section 6 with some remarks and open questions.

The dismountability technique can be generalized to multi-hop temporal paths. Here, we recall the ideas, referring again the reader to [13] for more details. Let $P^{-}$ be a temporal path from some node $u$ to some node $v$, such that this path arrives at $v$ through $e^{-}(v)$, then $u$ can delegate its emissions to $v$ in the same way as for $1$-hop dismountability. The edges along the path may or may not be locally earliest, what matters is only that the edge incident to $v$ is. Similarly, let $P^{+}$ be a temporal path from some node $w$ to $u$ that departs from $w$ through $e^{+}(w)$, then $w$ can reach $u$ after having been reached by all the other nodes. As before, we can now select the edges of both paths in the spanner, remove $u$ (and only $u$), and recurse in ${𝒢}^{\prime }:=𝒢\setminus \{u\}$. Whatever spanner exists in ${𝒢}^{\prime }$ plus the edges of the two paths will be a valid spanner of $𝒢$. The fact that one can recurse “obliviously” here (i.e. without taking into account which specific paths were used) is less immediate than before; in particular, the edge $e^{-}(v)$ may still exist in $𝒢\setminus \{u\}$ and $v$ could use it for reaching other nodes instead of departing from a local edge after $\lambda (e^{-}(v))$. However, this is not a problem, since a path from $u$ to that node would then be preserved, namely going from $u$ to $n^{-}(v)$ before $\lambda (e^{-}(v))$, then from $n^{-}(v)$ to these other nodes after $\lambda (e^{-}(v))$.

If both paths have length $\le k$ for some $k$, then $u$ is $k$-hop dismountable (and by extension, the graph is $k$-hop dismountable). See Figure 3 for an illustration.

When $k$-hop dismounting a node, the number of edges to be included in the spanner is at most $2k$. Thus, if a graph is recursively $k$-hop dismountable for some constant $k$, then this graph admits a spanner of size $O(n)$. Otherwise, the recursion stops at a point where the clique must have additional structure, which we characterize completely in this paper.

Let $V^{-}=\{n^{-}(v):v\in V\}$ be the nodes that are the earliest neighbor of at least one node, and $V^{+}=\{n^{+}(v):v\in V\}$ be the nodes that are the latest neighbor of at least one node. Finally, let $V^0=V\setminus (V^{-}\cup V^{+})$ be the nodes that are neither in $V^{-}$ nor in $V^{+}$.

Here, we summarize the obtained properties and show that they characterize (non) dismountability in a necessary and sufficient manner. Because non $\{1,2\}$-hop dismountable cliques could be of independent interest, we proceed in two steps, summarizing the structure of non $\{1,2\}$-hop dismountable cliques, then extending it to non $\{1,2,3\}$-hop dismountable cliques. Let $E^{-}=\{e^{-}(v):v\in V\}$ (resp. $E^{+}=\{e^{+}(v):v\in V\}$) be the set of edges that are earliest (latest) for at least one node. Then we have:

Let $𝒢$ be a temporal biclique as defined above. For completeness, this section recalls the strategy used in [3] to simplify the second part of the original proof and recover the $O(n\log n)$ result more elegantly. Let us denote here by $n$ the size of each part $V^{+}$ and $V^{-}$ (total size $2n$). The first component of the strategy is to divide the work into two parts, by splitting $V^{+}$ into two sets of nodes $X_1$ and $X_2$, each of size $n/2$, and recurse in two subproblems where the goal is to compute a spanner from $X_1$ to all of $V^{-}$, and a spanner from $X_2$ to all of $V^{-}$ (see Figure 10). The union of these two spanners ensures that every node of $V^{+}$ can reach all of $V^{-}$, which together with the matchings $M^{-}$ and $M^{+}$, guarantees that the resulting graph is temporally connected (as discussed above). The major observation is then that a one-sided version of dismountability can be used to reduce each of the subproblems until both parts have equal size. Indeed, as long as the target part (call it $T$, which is $V^{-}$ in the first step) is larger than the source part (call it $S$, which is $X_1$ or $X_2$ in the first step), then at least two nodes in $T$ have their latest neighbor coinciding in $S$. Thus, one of these nodes can delegate its receptions (relative to $S$) to the other, and be dismounted from the instance at the cost of selecting the corresponding two edges in the spanner. This is indeed sufficient because reachability from $S$ to $T$ is sufficient. One can then split the work, and recurse again.

In each step, dismountability may work beyond balancing the two parts, but in any case, it will work at least to that point. In each step, the number of selected edges when dismounting is $O(|T|)$, which yields the following recurrence on the size of a spanner: $size(n)\le 2\cdot size(n/2)+O(n)=O(n\log n)$ edges (by the master theorem).

The overall strategy permits a simple constructive algorithm to find $O(n\log n)$ spanners in temporal cliques based on dismountability only. This algorithm is summarized in Algorithm 1.

The search for $1$-hop or $2$-hop dismountable node can be done as follows. First, mark all the earliest and latest edge at every node. Then, for every node $v$, compute the subset of nodes that $v$ can reach in at most two hops, arriving through the earliest edge at these nodes (memorize at least one such path for each of these nodes), and compute the subset of nodes that can reach $v$ in at most two hops by departing through their latest edge (and memorize at least one such path). If both subsets are non-empty, then $v$ is $\{1,2\}$-hop dismountable through these paths. It is not hard to see that each of these steps runs in polynomial time, and so does the Bipartite_Spanner algorithm (Corollary 4.8 in [3]).

Let us start by defining the time-compressed version of a simple and proper temporal graph (not necessarily a clique) as follows.

In other words, every label of the graph is as small as it can be while preserving the local ordering among edges of $𝒢$. Figure 11 (left and middle) shows an example of temporal graph and its compressed version. (Again, this concept could be defined in more general settings than simple and proper graphs, bringing unnecessary complications to the present paper.)

For all matters concerning the reachability relation alone, temporal graphs and their time-compressed versions are equivalent because they have the same local ordering of the edges. Analysing the compressed version directly may be convenient.

An example of full-range graph is shown in Figure 11 (right). Observe that being full-range implies, among other things, that every label is used exactly once. In the following, we prove that full-range graphs in TC are pivotable and thus admit $O(n)$ spanners. Moreover, full-range cliques are $\{1,2,3\}$-hop dismountable. The following lemma is instrumental to both results.