PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings

Frank Kammer, Sandra Kiefer, Johannes Meintrup

arXiv:2610.30123v1cs.DScs.CCcs.DMmath.CO

TL;DR

Temporal exploration asks for a walk visiting every vertex, but connected temporal graphs have a tight quadratic worst-case bound. This paper uses 2-WL fibers to construct deterministic polynomial-time solutions for exploration and rendezvous, with improved bounds.

  • Problem

    Connected temporal graphs can require Θ(n^2) time steps for exploration, while several restricted settings still have substantial gaps between known upper and lower bounds.

    Source: §1 · p. 2

  • Method

    The paper uses the weaker symmetry information in 2-WL fibers to construct temporal walks for exploration and apply the approach to rendezvous.

    Source: §1 · p. 3, §7 · p. 30

  • Results

    The paper reports improved bounds for temporal exploration and rendezvous, with deterministic polynomial-time constructions.

    Source: §7 · p. 30

  • Takeaways & Limitations

    2-WL captures enough information about temporal walks between vertex pairs to replace the stronger use of automorphism orbits in these results.

    Source: §7 · p. 30

Abstract

from arXiv · show

Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with $n$ vertices can be explored in $O(qn\log^3(n))$ time steps, where $q$ is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small $q$, our bound substantially improves on the known worst-case bound of $\Theta(n^2)$ in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of $\Omega(n\log(n))$ when $q$ is constant and $\Omega(qn)$ when $1 \leq q \leq n$. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in $O(n\log^3(n))$ time steps, leaving a gap of only $\log^2(n)$ to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [ICALP'24] have shown an $O(rn^{1+\epsilon})$ bound for TEXP, for every fixed $\epsilon > 0$, where $r$ is the number of orbits, and an $O(n^{1+\epsilon})$ bound for TRP. Both results require superpolynomial computation time. Our contribution improves upon these results in several ways. First, the dependence on $n$ in the upper bounds on the number of time steps is decreased from $n^{1+\epsilon}$ to $n\log^3(n)$ for both TEXP and TRP. Second, for TEXP, we bound the number of time steps linearly by the parameter q, which is efficiently computable and upper bounded by $r$. Third, we provide novel deterministic polynomial-time algorithms for both TEXP and TRP.

1 Introduction

Temporal exploration remains difficult even in connected temporal graphs, where the known O(n^2) bound is tight and several restricted settings still have substantial upper–lower bound gaps. This paper uses 2-WL fibers as a weaker, efficiently computable symmetry parameter to obtain improved exploration and rendezvous bounds with deterministic polynomial-time constructions.

1 Introduction

  • Connected temporal graphs have a tight O(n^2) exploration bound, while several restricted classes still have widely separated upper and lower bounds.For bounded-degree, planar, and cycle settings, the cited lower bound is Ω(n log n), with upper bounds around n^3/2 up to logarithmic factors [18].Source: §1 · p. 2

1.1 Our Contribution

  • O(qn log^3 n) time steps suffice to explore a connected temporal graph, with a deterministic polynomial-time construction.Here q is the number of 2-WL fibers.Source: §1.1 · p. 4
  • The TEXP upper bound uses randomized walks over 2-WL fibers, whose structure supports balanced visit distributions; conditional-expectation derandomization yields a deterministic construction.Exploring each fiber in turn gives the full exploration result.Source: §1.1 · pp. 4–5
  • 2-WL fibers are a weaker symmetry notion than automorphism orbits, yet the resulting parameter q is at most the number r of orbits and is efficiently computable.The earlier orbit-based bound is O(rn^1+ε) for every fixed ε > 0 [38]; the new TEXP bound improves the dependence on n and has a deterministic polynomial-time construction.Source: §1 · pp. 2–3, §1.1 · p. 5
  • Ω(n log n) steps are necessary when q is constant, and Ω(qn) steps are necessary for some connected temporal graphs when 1 ≤ q ≤ n.The lower-bound constructions are drawn from known results [38].Source: §1.1 · p. 5
  • In the TRP setting, on connected temporal graphs with sufficiently large lifetime, two agents can always meet within O(n log^3 n) time steps using polynomial-time computation.This leaves a factor O(log^2 n) to the lower bound of Ω(n log n) [38].Source: §1.1 · p. 5

2 Detailed Technical Overview

This section develops phase-based exploration of 2-WL fibers using randomized recursive choices that preserve progress and can be derandomized. It applies single-fiber exploration to construct a polynomial-time rendezvous strategy in which agent a2 explores a fiber of size at most ⌈n/q⌉ in O(n log³ n) time steps.

2 Detailed Technical Overview

  • Exploration proceeds in phases over a fixed target set S, with buffer walks of at most n time steps connecting consecutive phase walks into one walk that visits all of S.A general progress guarantee for a fraction of the currently unvisited set can be repeatedly applied to obtain full exploration.Source: §2 · p. 6

2.1 From Automorphism Orbits to 2-WL

  • Unlike the orbit-based O(rn^(1+ε)) construction of Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [38], 2-WL fibers are polynomial-time computable but lack automorphisms’ repair mechanism.The 2-WL coloring encodes temporal-walk counts between vertex pairs, allowing equivalent vertices to share counts into other fibers.Source: §2.1 · pp. 6–7
  • The recursion chooses the right walk’s start uniformly from vertices reachable after the left walk, using 2-WL’s balanced transition probabilities to control collisions without automorphism-based repair.Biregularity of reachability between copies of a 2-WL fiber makes the transition matrix doubly stochastic; this supports the expected-progress analysis despite dependent recursive walks.Source: §2.1 · pp. 7–8, §2.2 · pp. 9–11

2.2 Randomized Partial Exploration

  • A phase walk visits Ω(|D_i| / log |S|) unvisited vertices in expectation within O(q|S| log |S|) time, yielding exploration of S in O(q|S| log^3 |S| + n log^2 |S|) time.Repeated phases remove a logarithmic fraction of the remaining vertices; the final O(log^2 |S|) vertices are visited individually, using O(n) time per vertex.Source: §2.1 · p. 8, §2.2 · pp. 11–12
  • Conditional expectations derandomize the recursive construction in polynomial time by fixing each random choice to preserve the expected number of distinct unvisited vertices reached.The algorithm maximizes E[Z_D − Q_D | σ] at each choice, where Z_D counts leaf visits in D and Q_D counts collisions.Source: §2.2 · p. 12

2.3 Temporal Rendezvous

  • O(n log^3 n) time steps suffice for polynomial-time rendezvous: both agents choose the same smallest 2-WL fiber, one waits there, and the other explores it.The agents can select the same fiber despite lacking a shared vertex labeling because the 2-WL coloring is canonical.Source: §2.3 · p. 12
  • O(n log^3 n) time steps suffice for agent a2 to explore S when |S| ≤ ⌈n/q⌉.The underlying graph and temporal edge labels are computed by scanning snapshots; 2-WL fibers take O(n^3 log n) time [61] after preprocessing labels into integer colors, including for edge-colored graphs. Temporal walks to S use standard temporal reachability algorithms [86].Source: §2.3 · p. 13

3 Preliminaries

The preliminaries define temporal walks and equitable partitions, then establish reachability bounds for connected temporal graphs. Equitable partitions allow reachability to be analyzed through a temporal quotient graph.

3 Preliminaries

  • A temporal walk is a time-ordered sequence of vertex-time pairs that waits or traverses an edge present at that step.Its time span is the difference between its final and initial times.Source: §3 · p. 13
  • In a connected temporal graph, the reachable set grows by at least one vertex per step until all vertices are reached, so any vertex can reach any other within n steps.The growth property is stated for a nonempty proper reachable set.Source: §3 · p. 13
  • For an equitable partition, the temporal quotient graph connects parts exactly when an edge between their vertices is active in that snapshot.Equitability requires each vertex in a part to have the same number of same-color neighbors in every part.Source: §3 · p. 13
  • A temporal walk between two parts in the quotient can be followed in the original graph, using equal neighbor counts to preserve reachability at each step.The quotient snapshots are connected, so a walk between parts is available within |P| time steps.Source: §3 · p. 14
  • For a part Pi of size |Pi|, at least h vertices of Pi become reachable from any u in Pi within O(min{hn/|Pi|, hr} + r) time steps.The two proved bounds are O(hn/|Pi| + r) and O(hr).Source: §3 · pp. 14–15

4 The Connection Between 2-WL and Temporal-Walk Counts

This section relates the 2-WL coloring of vertex pairs to temporal-walk counts. It shows that these counts are uniform within color classes, yielding biregular walk graphs and doubly stochastic transitions.

4 The Connection Between 2-WL and Temporal-Walk Counts

  • Within a 2-WL fiber, vertices have equal counts of each pair-color to and from every other fiber.The restricted color-count equalities are stated for both orientations.Source: §4 · p. 16
  • For vertex pairs with the same 2-WL color, the number of temporal walks between them is equal for every common start and end time.The proof obtains this by induction over the time span, decomposing walks by the vertex immediately before the final step.Source: §4 · pp. 16–17
  • For any two 2-WL fibers and times t ≤ t′, the weighted graph of temporal-walk counts and its support graph are both biregular.The weight for a vertex pair is its number of temporal walks between the specified times.Source: §4 · p. 17
  • Within a single fiber, every vertex has positive weighted degree and positive support-graph degree in the temporal-walk graph.This follows because each vertex can reach itself in one time step.Source: §4 · p. 17
  • Choosing uniformly among supported endpoints within one fiber gives a doubly stochastic transition matrix.Biregularity on the two copies of the same fiber makes every row and column sum to 1.Source: §4 · p. 18

5 Temporal Exploration via 2-WL Fibers

This section develops an exploration method that constructs walks for individual 2-WL fibers and repeatedly applies a partial-exploration procedure. It bounds the time for exploring all vertices by O(qn log^3 n) and for rendezvous by O(n log^3 n), with polynomial-time constructions for both.

5 Temporal Exploration via 2-WL Fibers

  • For each fiber S, the proof constructs a temporal walk visiting all its vertices; applying this result fiber by fiber yields Theorem 1.1.Small fibers are handled directly in O(n) time steps.Source: §5 · p. 18

5.1 Outline of the Procedure

  • A walk returned by PartialExplore(S, t) spans O(q|S| log |S|) time steps.The recursion tree has Θ(Kx) leaves for a subtree with exploration scale Kx, which helps bound the total span.Source: §5.1 · pp. 21–22

5.2 Analysis of the Procedure

  • Endpoint-transition and leaf-visit matrices are doubly stochastic throughout the recursive construction.With a uniformly random outermost start vertex, this implies that the vertex visited by any fixed leaf is uniformly distributed over S.Source: §5.2 · pp. 23–24
  • For every set D of desirable vertices, Algorithm 1 produces a walk with expected |V(W) ∩ D| at least γ|D| log |S|, for a constant γ > 0.The argument subtracts expected collisions from leaf visits; choosing the recursion parameter sufficiently large bounds collisions by half the expected leaf visits.Source: §5.2 · pp. 26–27

5.3 Derandomization via Conditional Expectations

  • Conditional expectations derandomize Algorithm 1 in polynomial time while preserving the randomized construction’s lower bound on Z_D − Q_D.The conditional expectation can be evaluated in polynomial time using matrix multiplications for leaf and leaf-pair visit probabilities.Source: §5.3 · p. 28

5.4 Putting it All Together

  • For each 2-WL fiber S, a polynomial-time deterministic walk visits all its vertices in O(q|S| log^3 |S| + n log^2 n) time steps.The construction repeatedly visits unvisited vertices in phases, then covers the remaining vertices and connects the phases.Source: §5.4 · pp. 28–29
  • O(qn log^3 n) time steps suffice to explore every vertex, and two agents can meet within O(n log^3 n) steps, with polynomial computation time for both.The exploration bound uses q, the number of 2-WL fibers.Source: §5.4 · p. 29

6 Lower Bounds for Temporal Exploration

Known temporal-graph constructions yield exploration lower bounds of Ω(qn) for 1 ≤ q ≤ n and Ω(n log n) when q is constant. The bounds adapt constructions based on star snapshots and on single-orbit graphs, respectively.

6 Lower Bounds for Temporal Exploration

  • Ω(n²) time steps are required by a construction whose snapshots are stars with a center cycling through one vertex set and another set always as leaves.The construction requires Ω(|V1| · |V2|) = Ω(n²) steps to explore.Source: §6 · p. 29
  • Ω(rn) time steps are required for every 1 ≤ r ≤ n by adjusting the star-based construction to have r automorphism orbits.For r > n/2, the construction adds a final snapshot to split the leaf set's orbit while preserving the Ω(n²) lower bound.Source: §6 · p. 29
  • Ω(qn) time steps are required for every 1 ≤ q ≤ n, by adapting an orbit-based construction so its 2-WL fiber count is q.The construction uses the fact that its 2-WL fibers coincide with its automorphism orbits.Source: §6 · pp. 29–30
  • Ω(n log n) time steps are required when q is constant, by extending a single-orbit construction with a path factor that creates a constant number of 1-WL distance classes.The path factor introduces r distance classes from its ends, which color refinement detects.Source: §6 · p. 30

7 Conclusion

The paper introduces 2-WL fibers as a structural parameter for temporal exploration and rendezvous, using pairwise information to improve bounds while retaining polynomial-time algorithms. It also identifies directions for testing how WL captures temporal reachability and other agent problems.

7 Conclusion

  • 2-WL captures enough information about temporal walks between vertex pairs to replace the stronger use of automorphism orbits, yielding improved bounds and polynomial-time algorithms.The authors introduce 2-WL fibers as a structural parameter for temporal exploration and rendezvous.Source: §7 · p. 30
  • The authors expect 2-WL to capture temporal reachability exactly in proper temporal graphs, where no two incident edges appear at the same time step.They propose investigating whether pairs indistinguishable by 2-WL have the same temporal-reachability behavior.Source: §7 · p. 30
  • Because 2-WL fibers suffice for two agents without a common labeling to meet quickly, the authors propose studying WL fibers in other temporal agent problems.Suggested directions include temporal cops-and-robbers variants and problems involving reachability, connectivity, and temporal spanning structures.Source: §7 · p. 30
  • The authors identify the limitations of 1-WL for exploration and rendezvous as an open question, noting that their approaches rely on pairwise information and temporal-walk counts.They anticipate that a 1-WL-based approach would require a substantially different method.Source: §7 · p. 30

Related papers

Loading 2610.30123v1…