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).