Temporal graph walks made faster using color pattern techniques
Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
Summary
The paper studies how to travel through changing networks where connections appear and disappear over time, aiming to visit all locations efficiently. The authors use a coloring method called 2-dimensional Weisfeiler-Leman (2-WL) to group similar parts of the network, which helps them find shorter routes than previously known. They also tackle the problem of two agents trying to meet in such a network without communicating and give algorithms that work in reasonable time for both problems. Their methods improve on past results by reducing how long these tasks take and providing practical ways to find the routes.
What this means in practice
- •For network schedulers: Design faster schedules for visiting all nodes in time-varying networks using color pattern analysis to reduce traversal steps.
- •For robot coordination teams: Generate efficient meeting strategies for multiple robots navigating changing connection networks without communication.
Authors
Frank Kammer, Sandra Kiefer, Johannes Meintrup
Abstract
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 $Θ(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 $Ω(n\log(n))$ when $q$ is constant and $Ω(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+ε})$ bound for TEXP, for every fixed $ε> 0$, where $r$ is the number of orbits, and an $O(n^{1+ε})$ 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+ε}$ 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.