← 研踪 PaperTrailarXiv:2608.26952 · v3
On the Instance Optimality of Bidirectional Dijkstra's Algorithm
首次提交 2026-08-27 18:53
版本更新 2026-11-03 22:48
雷达观测 2026-11-04 23:39
摘要
We study instance optimality for the shortest $st$-path problem on positive-weight graphs, emphasizing how graph structure and query access determine the cost of certifying shortest paths. For undirected simple graphs in the standard adjacency-list model, we prove instance-sensitive lower bounds against all randomized algorithms that are correct on every admissible input. A quantitative reservoir argument bounds the instance-optimality ratio of corrected bidirectional Dijkstra in terms of its exploration size and the vertex count. A tensor-graph reduction translates low-query explored edges into vertex-cover constraints, yielding sufficient conditions through optimizable explored cores, degree moments, exploration orientations, and auxiliary degree profiles. We also derive bounds using exceptional high-degree vertices and weight-critical edges, and prove that a superconstant speedup over bidirectional Dijkstra requires all but a vanishing fraction of explored edges in each direction to concentrate around sublinear vertex sets. We also introduce a local-discovery model in which algorithms initially know only the terminal handles, cannot query undiscovered vertices or obtain the vertex count, but may make degree queries at discovered vertices. In this model, corrected bidirectional Dijkstra is constant-factor instance-optimal on directed and undirected positive-weight simple graphs, including with incoming and outgoing degree queries, for every fixed adjacency ordering. Finally, we revisit the correction to the original update rule and give a self-contained proof of the corrected multigraph guarantee.
作者备注：43 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-03 22:48 · 最新观测版本
On the Instance Optimality of Bidirectional Dijkstra's Algorithm
We study instance optimality for the shortest $st$-path problem on positive-weight graphs, emphasizing how graph structure and query access determine the cost of certifying shortest paths. For undirected simple graphs in the standard adjacency-list model, we prove instance-sensitive lower bounds against all randomized algorithms that are correct on every admissible input. A quantitative reservoir argument bounds the instance-optimality ratio of corrected bidirectional Dijkstra in terms of its exploration size and the vertex count. A tensor-graph reduction translates low-query explored edges into vertex-cover constraints, yielding sufficient conditions through optimizable explored cores, degree moments, exploration orientations, and auxiliary degree profiles. We also derive bounds using exceptional high-degree vertices and weight-critical edges, and prove that a superconstant speedup over bidirectional Dijkstra requires all but a vanishing fraction of explored edges in each direction to concentrate around sublinear vertex sets. We also introduce a local-discovery model in which algorithms initially know only the terminal handles, cannot query undiscovered vertices or obtain the vertex count, but may make degree queries at discovered vertices. In this model, corrected bidirectional Dijkstra is constant-factor instance-optimal on directed and undirected positive-weight simple graphs, including with incoming and outgoing degree queries, for every fixed adjacency ordering. Finally, we revisit the correction to the original update rule and give a self-contained proof of the corrected multigraph guarantee.
查看此版本解读 →查看此版本原文 ↗