The directed temporal exploration problem
Abstract
We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of O(n2) suffices to guarantee the existence of a temporal exploration on always-unilateral temporal digraphs. We complement this with a Ω(n2) lower bound, even in the case where each snapshot has maximum undirected degree 2; for always-strong temporal digraphs, the lower bound still holds even if the maximum undirected degree is 3. This stands in stark contrast with the undirected setting. For the large minimum degree setting, we show that a lifetime of $4n/3 - 1$ is sufficient and necessary for guaranteeing the existence of a temporal exploration on temporal digraphs where each snapshot is semicomplete. For always-strong temporal digraphs where each snapshot has minimum undirected degree at least $n - c - 1$, we prove that a lifetime of O(cn) guarantees the existence of a temporal exploration, and we also prove that this is asymptotically tight. From a computational perspective, our results for temporal semicomplete digraphs also yield a polynomial-time, factor-4/3 algorithm for deciding if a temporal semicomplete digraph admits a temporal exploration within the first ℓ snapshots. We complement this showing that no polynomial-time, factor-$(4/3 - ε)$ approximation algorithm exists, even if every snapshot is a tournament, unless P=NP.
Related
- Beyond Search-Imitation: Prior-Directed Exploration for Searchless Chess
- Algorithmic exploration of the unit distance problem in the rational plane
- Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
- The Renormalization Group as a Stochastic Exploration Process
- An Exploration of Lacunary Orthogonal Polynomials Associated with the Geronimus Transformation
BibTeX
@misc{milani2026directed,
title = {{The directed temporal exploration problem}},
author = {Marcelo Garlet Milani and Lucas Picasarri-Arrieta and Chaoliang Tang and Hehui Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.34339},
eprint = {2609.34339},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34339},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The directed temporal exploration problem
AU - Marcelo Garlet Milani
AU - Lucas Picasarri-Arrieta
AU - Chaoliang Tang
AU - Hehui Wu
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2609.34339
UR - https://arxiv.org/abs/2609.34339
AB - We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of O(n^2) suffices to guarantee the existence of a temporal exploration on always-unilateral temporal digraphs. We complement this with a Ω(n^2) lower bound, even in the case where each snapshot has maximum undirected degree 2; for always-strong temporal digraphs, the lower bound still holds even if the maximum undirected degree is 3. This stands in stark contrast with the undirected setting. For the large minimum degree setting, we show that a lifetime of $4n/3 - 1$ is sufficient and necessary for guaranteeing the existence of a temporal exploration on temporal digraphs where each snapshot is semicomplete. For always-strong temporal digraphs where each snapshot has minimum undirected degree at least $n - c - 1$, we prove that a lifetime of O(cn) guarantees the existence of a temporal exploration, and we also prove that this is asymptotically tight. From a computational perspective, our results for temporal semicomplete digraphs also yield a polynomial-time, factor-4/3 algorithm for deciding if a temporal semicomplete digraph admits a temporal exploration within the first ℓ snapshots. We complement this showing that no polynomial-time, factor-$(4/3 - ε)$ approximation algorithm exists, even if every snapshot is a tournament, unless P=NP.
ER -