Source-linked AI summary
On Temporal Graph Exploration
Thomas Erlebach, Michael Hoffmann, Frank Kammer
TL;DR
The paper studies foremost exploration of temporal graphs, where edges change over time and the goal is to visit all vertices as early as possible. It proves hardness and gives bounds for restricted underlying graphs and online settings, then applies random-temporal-graph exploration to gossiping.
Problem
TEXP asks for the earliest-arrival walk that visits every vertex in a temporal graph, with connectedness assumed in the main offline setting.
Source: §1 · p. 2, §2.1 · p. 6Method
The paper develops exploration results for general temporal graphs, restricted underlying graph classes, and online settings, including a multi-agent-to-single-agent reduction.
Source: §1 · p. 3, §2.2 · p. 7Results
The paper proves NP-hardness of O(n^(1−ε))-approximation for every ε > 0, gives class-specific exploration bounds, and obtains online bounds of O(m) or O(m log n) steps.
Source: §1 · p. 3Takeaways & Limitations
The random-temporal-graph exploration algorithm yields gossiping with O(m log n) messages per instance after O(m log^2 n) initialization.
Source: §1 · p. 4For planar graphs, the known Ω(n log n) lower bound and O(n^1.8 log n) upper bound leave tight exploration bounds open.
Source: §8 · p. 27
Abstract
from arXiv · showhide
A temporal graph is a graph in which the edge set can change from one time step to the next. The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. In the first part of the paper, we consider only undirected temporal graphs that are connected at each time step. For such temporal graphs with $n$ nodes, we show that it is \NP-hard to approximate TEXP with ratio $O(n^{1-\varepsilon})$ for every $\varepsilon>0$. We also provide an explicit construction of temporal graphs that require $\Theta(n^2)$ time steps to be explored. In the second part of the paper, we still consider temporal graphs that are connected in each time step, but we assume that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one time step) belongs to a specific class of graphs. Among other results, we show that temporal graphs can be explored in $O(n^{1.5}k^{1.5}\log n)$ time steps if the underlying graph has treewidth $k$, in $O(n^{1.8}\log n)$ time steps if the underlying graph is planar, and in $O(n\log^3 n)$ time steps if the underlying graph is a $2\times n$ grid. In the third part of the paper, we consider settings where the graphs in future time steps are not known and the exploration schedule is constructed online. We replace the connectedness assumption by a weaker assumption and show that $m$-edge temporal graphs with regularly present edges and with probabilistically present edges can be explored online in $O(m)$ time steps and $O(m \log n)$ time steps with high probability, respectively. We finally show that the latter result can be used to obtain a distributed algorithm for the gossiping problem in random temporal graphs.
1 Introduction
TEXP asks for the earliest-arrival temporal walk that visits every vertex, and prior approximation bounds left a substantial gap. The paper establishes hardness and exploration bounds across general, restricted-underlying-graph, and online settings, and applies its random-temporal-graph algorithm to gossiping.
1 Introduction
- TEXP seeks a temporal walk from a start vertex that visits every vertex with the earliest arrival time; each time step permits waiting or traversing a currently present edge.Unless considering the online variant, the algorithm knows the graphs at all time steps in advance.Source: §1 · p. 2
- Under the standard connectedness assumption, every time-step graph is connected, and the paper assumes a lifetime of at least |V|^2.Without that assumption, deciding whether exploration is possible is NP-complete; prior work gives an n^2 arrival-time bound under connectedness.Source: §1 · p. 2
- TEXP is NP-hard to approximate within O(n^(1−ε)) for every ε > 0, and some temporal graphs require Θ(n^2) exploration steps.The paper also proves hardness within O(∆^(1−ε)) when the underlying graph has degree ∆ = Ω(n^δ) for any constant δ > 0.Source: §1 · p. 3
- For restricted underlying graphs, exploration takes O(n^1.5 k^1.5 log n) steps at treewidth k, O(n^1.8 log n) for planar graphs, and O(n log^3 n) for a 2×n grid.Cycles and cycles with a chord admit O(n)-step exploration; a bounded-degree planar example with path snapshots requires Ω(n log n) steps.Source: §1 · p. 3
- Online exploration of m-edge temporal graphs takes O(m) steps with regularly present edges or O(m log n) steps with probabilistically present edges, the latter with high probability.These settings do not provide full knowledge of future edges.Source: §1 · p. 3
- For sparse graphs, gossiping uses O(m log n) messages per instance after O(m log^2 n) initialization, only O(log n) above the Ω(n) message lower bound.The algorithm applies to n-vertex m-edge graphs that are “connected” in a certain sense.Source: §1 · p. 4
1.1 Related work
- Prior work spans temporal paths, connectivity, network design, and exploration; Erlebach et al. give O(n^1.75)-step exploration for bounded-degree snapshots or two moves per step.Other exploration work considers temporal rings, distributed temporal rings [12], and cacti.Source: §1.1 · p. 5
2 Preliminaries
The preliminaries define temporal realizations, foremost exploration, and the full-information and online settings. They establish reachability and structural reductions used to derive exploration schedules from multi-agent schedules and from component-wise solutions.
2.1 Definitions
- A foremost exploration schedule starts at s at time 0, visits every vertex, and minimizes the time the last unvisited vertex is reached.TEXP uses a temporal graph with lifetime at least |V|^2; k-TEXP allows k agents starting at s.Source: §2.1 · p. 6
- In Sections 2–4 the algorithm knows all time-step graphs, while Sections 5–7 study online settings without full knowledge of future graphs.The underlying graph is the union of all edges appearing during the temporal graph's lifetime.Source: §2.1 · p. 6
2.2 Preliminary Results
- If every consecutive time step in a window of k−1 steps contains a path between u and v inside a k-vertex set H, an agent can move from u to v within that window.The reachable set grows by at least one vertex per step until v is reached.Source: §2.2 · p. 7
- If each of k agents explores within t steps, one agent can explore within O((t+n)k log n) steps by repeating phases and copying the agent that covers the most remaining vertices.Each phase uses t exploration steps plus n steps for agents to return to the start; it reduces unexplored vertices by a factor of 1−1/k.Source: §2.2 · p. 7
- Exploration bounds transfer from a graph to its connected subgraphs, edge contractions, and connected minors, while a bounded number of contractions preserves O(t(n′)) time under the stated growth conditions.The bounds follow by suppressing missing edges or contracted-edge moves and applying the contraction result.Source: §2.2 · pp. 7–8
- For graphs assembled from biconnected blocks, depth-first traversal of the block-cut tree gives an O(d|V| + Σt(|Vi|)) exploration bound when block vertices have degree at most d.Each block is explored on first visit and traversed at most d times; each traversal uses at most the block's vertex count in steps.Source: §2.2 · p. 9
3 Inapproximability Results for General and Bounded-Degree Temporal Graphs
The section establishes strong inapproximability for temporal graph exploration, including on planar graphs of maximum degree 3, and gives constructions with quadratic exploration time [p38, p33, p39].
3 Inapproximability Results for General and Bounded-Degree Temporal Graphs
- For every n, an explicit family of temporal graphs requires Ω(n²) exploration steps, and for every k = o(n), some n-vertex instances require at least Ω(n²/k) steps with k agents.In the construction, moving between designated leaves takes r + 1 time steps; the multi-agent bound follows by serializing agents with reset overhead.Source: §3 · pp. 9–10
- For every even d ≥ 4, some temporal graphs with underlying maximum degree d require Ω(gd²) steps to explore, despite having Θ(gd) vertices.The construction also lets all center vertices be explored from any starting vertex in at most g(2d − 1) steps.Source: §3 · p. 11
- For every d ≥ 2, an infinite family with underlying maximum degree at most d requires Ω(dn) exploration steps.For d = 2 or 3 the construction is a static path; for larger d it follows from Proposition 3.3.Source: §3 · p. 12
- TEXP is NP-hard on temporal graphs whose underlying graphs are planar and have maximum degree 3.The reduction encodes Hamiltonian s-t path: an exploration in n′ − 1 steps exists exactly when the source graph has such a path.Source: §3 · p. 12
- Approximating TEXP within O(n^(1−ε)) is NP-hard for every constant ε > 0.The reduction distinguishes instances explorable in n steps from those requiring Ω(n^(2−ε)) steps.Source: §3 · pp. 13–14
- Approximating TEXP within O(∆^(1−ε)) is NP-hard for every ε, even when the underlying graph has maximum degree ∆ = Ω(n^δ).The reduction yields a gap between exploration in at most 4n steps and a lower bound of Ω(∆n^(1−γ)).Source: §3 · pp. 14, 16
4 Restricted Underlying Graphs
This section studies fully known temporal graphs that remain connected at each time step but have restricted underlying graphs. It addresses the difficulty of exploration by establishing both lower bounds and class-specific exploration guarantees.
4.1 Lower Bound for Planar Bounded-Degree Graphs
- Ω(n log n) steps can be necessary even when the underlying graph is planar with maximum degree 4 and every time-step graph is a simple path.The construction requires Ω(log n) rounds of Θ(n) steps before all vertices are visited.Source: §4.1 · pp. 16–18
4.2 Underlying Graphs with Small Separators
- O((n^2b/r + nrb^2) log n) steps suffice when the underlying graph’s class admits an (r, b)-division.The method explores components one by one using boundary agents, then converts the multi-agent schedule to one agent.Source: §4.2 · p. 18
- O(n^1.5k^1.5 log n) steps suffice for underlying graphs of treewidth at most k, while O(n^1.8 log n) suffice for planar underlying graphs.These bounds follow by applying the division-based exploration result to the respective graph classes.Source: §4.2 · pp. 19–20
4.3 Cycles and Cycles with Chords
- 2n−2 steps suffice to explore every temporal cycle, and some cycles require at least 2n−3 steps.The paper also gives a polynomial-time algorithm for an optimal cycle schedule; temporal trees of rings with a constant number of cut nodes per cycle admit O(n)-step exploration.Source: §4.3 · pp. 20–21
- O(n) time steps suffice for a temporal cycle with one chord.The proof separates cases according to how often the chord is present in the first 7n steps.Source: §4.3 · p. 21
4.4 The 2 × n Grid
- O(n log n) steps with 4 log n agents, or O(n log^3 n) steps with one agent, suffice for a temporal 2 × n grid.The multi-agent method recursively explores grid halves while corner agents move inward and other agents explore the unvisited subgrid.Source: §4.4 · pp. 21–22
5 Temporal Graphs with Regularly Present Edges
This section studies online exploration when edges are regularly present, dropping the connectedness assumption in favor of a guarantee on edge availability across every cut. A minimum-spanning-tree traversal yields an O(m)-time-step exploration schedule.
5 Temporal Graphs with Regularly Present Edges
- The online setting drops connectedness at every time step and instead requires an edge across every cut on average at least once every c time steps.For each edge e, Ie bounds the consecutive time steps during which e can be absent.Source: §5 · pp. 22–23
- O(m) time steps suffice to explore an n-vertex, m-edge temporal graph online when its edges are regularly present.The algorithm knows each edge's availability bound but not its future schedule.Source: §5 · pp. 22–23
- The schedule follows an Euler tour of a minimum spanning tree weighted by each edge's largest power-of-two bound on absence.If a tour edge is absent, the agent waits until it becomes available; crossing edge e takes at most Ie ≤ 2Je time steps.Source: §5 · p. 23
- The O(m) bound follows by charging tree-edge weights to component-boundary edges, bounding each edge's total charge, and summing over the m underlying edges.For each weight scale, components formed by removing tree edges of that weight assign charges to edges leaving them.Source: §5 · p. 23
6 Random Temporal Graphs
For random temporal graphs with independent edge presences, this section replaces per-step connectedness with a lower bound on the total presence probabilities across every cut. It gives an online Euler-tour exploration schedule with an O(m log n) time bound that holds with high probability.
6 Random Temporal Graphs
- The model assumes each edge exists independently in each time step and requires the sum of edge probabilities across every cut to be at least 1/c.The graph need not be connected in each time step.Source: §6 · pp. 23–24
- O(m log n) time steps suffice with probability at least 1 − 1/n^d for any constant d ≥ 1.The schedule traverses an Euler tour of a minimum spanning tree weighted by Ie = 1/pe.Source: §6 · p. 24
- The algorithm weights each edge by 1/pe and bounds the chance that it is absent throughout an interval of ⌈ℓ/pe⌉ steps by exp(−ℓ).Choosing ℓ = 3d·ln n gives the stated high-probability bound; the resulting exploration time is O(m log n).Source: §6 · p. 24
- The cut-probability assumption implies the weighted cut condition used in the regularly-present-edges analysis.For each cut S, the sum of c·pe over crossing edges is at least 1.Source: §6 · p. 24
7 Application: Gossiping Problem
The section applies random-temporal-graph exploration to distributed gossiping, where each processor must send its initial value to all others. It first builds a probability-weighted minimum spanning tree, then uses its Euler tour to exchange values.
7 Application: Gossiping Problem
- In the model, edges appear independently with probabilities pe, each vertex knows its incident-edge probabilities, and probability mass across every cut is at least 1/c.Processors hold initial values, and gossiping means distributing each value to all other processors.Source: §7 · pp. 24–25
- The algorithm builds a minimum spanning tree with edge weights 1/pe, then traverses its Euler tour twice to collect and distribute processor values.The constructed tree can be reused for further gossiping instances without recomputing it.Source: §7 · pp. 25, 27
- The probability-weighted minimum spanning tree can be built using O(m log^2 n) messages with probability at least 1 − 1/n^(d−1).The construction adapts the Gallager–Humblet–Spira algorithm and proceeds in phases with distributed components.Source: §7 · p. 25
- Each construction phase selects minimum-weight outgoing edges for components, exchanges component information through tokens, and reduces the component count by half.Messages are sent over edges used by the final tree's Euler tour; the analysis bounds the total across ⌈log n⌉ phases.Source: §7 · pp. 26–27
- After building a minimum spanning tree, gossiping takes O(m log n) messages per instance with probability at least 1 − 2/n^d.Building the tree takes O(m log^2 n) messages with probability at least 1 − 1/n^(d−1).Source: §7 · p. 27
8 Conclusion
The conclusion frames temporal-graph methods as a developing toolbox and identifies unresolved bounds and algorithmic questions for restricted underlying graphs.
8 Conclusion
- The study of temporal graphs still lacks the intuition and range of techniques developed for static graphs, and the authors hope their methods will help build a toolbox.They cite the general conversion of multi-agent solutions to single-agent solutions as an example.Source: §8 · p. 27
- Tight exploration bounds remain open for grids, bounded-degree graphs, and planar graphs, and optimal polynomial-time solvability for further underlying-graph classes is also an open question.For planar graphs, the paper gives an O(n^1.8 log n) upper bound and an Ω(n log n) lower bound for a specific planar, bounded-degree family.Source: §8 · p. 27