Metraipolis › archive › dc_6b3eaa29bc6c

The directed temporal exploration problem — arXiv:2609.34339

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.34339
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:31.430Z
SHA-256 of the archived text
d146a5f15a4927b0cd39619a3af5978c15234e537dbefa5ae41e631ca832e68a
Stable URL of this page
https://metraipolis.com/documento/dc_6b3eaa29bc6c

How to cite

The directed temporal exploration problem — arXiv:2609.34339 — arXiv (en), https://arxiv.org/abs/2609.34339 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6b3eaa29bc6c (Metraipolis archive dc_6b3eaa29bc6c, sha256 d146a5f15a4927b0cd39619a3af5978c15234e537dbefa5ae41e631ca832e68a)
BibTeX
@misc{dc6b3eaa29bc6c,
  title = {The directed temporal exploration problem — arXiv:2609.34339},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.34339},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6b3eaa29bc6c; sha256 d146a5f15a4927b0cd39619a3af5978c15234e537dbefa5ae41e631ca832e68a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34339. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(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 $\ell$ snapshots. We complement this showing that no polynomial-time, factor-$(4/3 - \epsilon)$ approximation algorithm exists, even if every snapshot is a tournament, unless P$=$NP.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.34339 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.916Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).