Metraipolis › archive › dc_55334a23ea02
On the Instance Optimality of Bidirectional Dijkstra's Algorithm — arXiv:2608.26952
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.26952
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T19:19:12.038Z
- SHA-256 of the archived text
709f99de59e0ea53f977b507f707d6735a4466b2876b04f6766fe32a4917a277- Stable URL of this page
https://metraipolis.com/documento/dc_55334a23ea02
How to cite
On the Instance Optimality of Bidirectional Dijkstra's Algorithm — arXiv:2608.26952 — arXiv (en), https://arxiv.org/abs/2608.26952 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_55334a23ea02 (Metraipolis archive dc_55334a23ea02, sha256 709f99de59e0ea53f977b507f707d6735a4466b2876b04f6766fe32a4917a277)
BibTeX
@misc{dc55334a23ea02,
title = {On the Instance Optimality of Bidirectional Dijkstra's Algorithm — arXiv:2608.26952},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.26952},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_55334a23ea02; sha256 709f99de59e0ea53f977b507f707d6735a4466b2876b04f6766fe32a4917a277},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26952. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Recent work by Haeupler, Hladík, Rozhon, Tarjan, and Tětek on the instance optimality of shortest-path algorithms established several results concerning Dijkstra's algorithm and bidirectional Dijkstra's algorithm in weighted and unweighted graphs. Motivated by these results, we revisit the question of instance optimality for shortest $st$-path algorithms in the standard query model. We identify several issues in the analysis of the instance optimality of both unidirectional and bidirectional Dijkstra's algorithms and provide corresponding counterexamples. We then propose a minimal simple modification of the bidirectional Dijkstra algorithm and prove that the resulting variant is instance optimal in the weighted setting. Furthermore, we revisit the unweighted case, provide a simplified proof of the lower bound showing that no algorithm can achieve instance optimality up to a factor better than $O(\Delta)$, where $\Delta$ denotes the maximum degree of the graph, and discuss the implications of this result for approximation algorithms. Finally, we make progress on the open problem of instance optimality in simple graphs. We show that if the problem instance satisfies $n\ge m/16$, where $n$ is the number of nodes and $m$ is the number of edges queried by our algorithm, then it is optimal up to a constant factor. Additionally, we show instance optimality for a broad class of instances, in particular when the largest degree in the graph is at most the square root of the number of explored edges, our algorithm exhibits optimality up to a constant factor. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2608.26952 — 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-17T19:16:36.839Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).