Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
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(qnlog3(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 Θ(n2) in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of Ω(nlog(n)) when q is constant and Ω(qn) when 1 ≤ q ≤ 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(nlog3(n)) time steps, leaving a gap of only log2(n) to the known lower bound. Dogeas, Erlebach, Kammer, Meintrup, and Moses Jr. [ICALP'24] have shown an O(rn1+ε) bound for TEXP, for every fixed ε> 0, where r is the number of orbits, and an O(n1+ε) 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 n1+ε to nlog3(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.
Related
- An infinite family of intransitive directed strongly regular graphs with rank 6 Weisfeiler--Leman closure
- Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
- Transfer of Weisfeiler-Leman equivalence under graph operations
- The directed temporal exploration problem
- Quantum-assisted rendezvous on hypercubes: a quantum Bernoulli noise approach
BibTeX
@misc{kammer2026temporal,
title = {{Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings}},
author = {Frank Kammer and Sandra Kiefer and Johannes Meintrup},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30123},
eprint = {2610.30123},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30123},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
AU - Frank Kammer
AU - Sandra Kiefer
AU - Johannes Meintrup
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30123
UR - https://arxiv.org/abs/2610.30123
AB - 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(qnlog^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 Ω(nlog(n)) when q is constant and Ω(qn) when 1 ≤ q ≤ 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(nlog^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 nlog^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.
ER -