Metraipolis › archive › dc_2195cbc97c09
Bottleneck Paths Reduce to Deterministic Graphical Games and a Counterexample to a Claimed Linear-Time Algorithm — arXiv:2608.04279
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.04279
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:58:19.778Z
- SHA-256 of the archived text
c4abbd78626506b52f6d97606efd20316652b0859ebc4ed4f5881e56b865f1db- Stable URL of this page
https://metraipolis.com/documento/dc_2195cbc97c09
How to cite
Bottleneck Paths Reduce to Deterministic Graphical Games and a Counterexample to a Claimed Linear-Time Algorithm — arXiv:2608.04279 — arXiv (en), https://arxiv.org/abs/2608.04279 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2195cbc97c09 (Metraipolis archive dc_2195cbc97c09, sha256 c4abbd78626506b52f6d97606efd20316652b0859ebc4ed4f5881e56b865f1db)
BibTeX
@misc{dc2195cbc97c09,
title = {Bottleneck Paths Reduce to Deterministic Graphical Games and a Counterexample to a Claimed Linear-Time Algorithm — arXiv:2608.04279},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.04279},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2195cbc97c09; sha256 c4abbd78626506b52f6d97606efd20316652b0859ebc4ed4f5881e56b865f1db},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04279. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Chechik, Kaplan, Thorup, Zamir, and Zwick (STACS 2016) claimed a simple deterministic linear-time comparison-based algorithm for solving deterministic two-player, turn-based, zero-sum terminal-payoff games, also known as deterministic graphical games (DGGs). We give a counterexample to their algorithm. We also give a deterministic linear-time reduction from the directed $s$-$t$ bottleneck path (BP) problem to the DGG problem. Consequently, a linear-time comparison-based algorithm for computing the value of a designated start vertex in a DGG would yield a linear-time comparison-based algorithm for directed $s$-$t$ BP. Whether directed $s$-$t$ BP admits such an algorithm has remained open since Gabow and Tarjan gave their $\mathcal{O}(m\log^* n)$-time algorithm. Thus, a positive resolution of the open question for DGGs would also resolve the corresponding open question for directed $s$-$t$ BP.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.04279 — 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-31T11:47:39.818Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).