Metraipolis › archive › dc_bcbef2125491
Instance-Optimality of Bidirectional Dijkstra on Simple Graphs — arXiv:2608.24380
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.24380
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T07:03:48.596Z
- SHA-256 of the archived text
c2d67b69ebddf05f09eca504cb800a34b9723220bf62903819a47b1032368cec- Stable URL of this page
https://metraipolis.com/documento/dc_bcbef2125491
How to cite
Instance-Optimality of Bidirectional Dijkstra on Simple Graphs — arXiv:2608.24380 — arXiv (en), https://arxiv.org/abs/2608.24380 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bcbef2125491 (Metraipolis archive dc_bcbef2125491, sha256 c2d67b69ebddf05f09eca504cb800a34b9723220bf62903819a47b1032368cec)
BibTeX
@misc{dcbcbef2125491,
title = {Instance-Optimality of Bidirectional Dijkstra on Simple Graphs — arXiv:2608.24380},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.24380},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bcbef2125491; sha256 c2d67b69ebddf05f09eca504cb800a34b9723220bf62903819a47b1032368cec},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.24380. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hladík, Rozhoň, Tarjan, and Tětek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-26 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.24380 — 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-18T07:01:33.497Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-26?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).