Instance-optimality of bidirectional Dijkstra on simple weighted graphs
Let be a simple graph, directed or undirected, with positive real-valued edge weights, and let . When the graph is accessed through vertex and incident-edge queries, is bidirectional Dijkstra instance-optimal for computing the shortest-path distance , both in the order-oblivious model, where incident edges are presented in a random order, and in the order-dependent model, where their order is fixed and accessible to the algorithm?
References
Primary source
Additional references
Progress summary
A new paper claims that the answer depends on how graphs are accessed, proving a positive result in one simple-graph setting but separating other settings.
The problem asks whether bidirectional Dijkstra is always as efficient as the best algorithm tailored to the particular simple weighted graph. A 2024 result established this for weighted multigraphs, but explicitly left the simple-graph extension open.
Known results
- Weighted multigraphs, including directed and undirected graphs: instance optimality was proved in 2024; the authors left the simple-graph extension open.
- Unweighted multigraphs: instance optimality is possible only up to a factor of , and this factor is necessary.
August 25, 2026 model-sensitive results
An arXiv work claims instance optimality for simple undirected graphs under random incident-edge order, separations in directed settings, and lower bounds for competing algorithms. Thus it claims substantial progress on the simple-graph question, while showing that the answer depends on directedness and on whether access order may be used; the claims have not been independently verified here.
Current status (as of August 2026): A new work claims resolution in specific simple-graph access models, but the general model-sensitive picture and the reported results remain unverified.
Solutions 0
No solutions have been posted yet.