# Almost Optimal Multiple Source Shortest Paths and Reachability

Preprint · Barna Saha, Yinzhan Xu, Christopher Ye

- Archive id: arxiv:2606.26554
- Published: 2026-06-25
- arXiv: https://arxiv.org/abs/2606.26554
- Source URL: https://arxiv.org/abs/2606.26554
- PDF: https://arxiv.org/pdf/2606.26554
- Provenance: arxiv

## Abstract

Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweighted graphs, while computing single-source shortest path (SSSP) requires $O(n^2)$ time in dense graphs, all-pairs shortest paths (APSP) can be computed in $\\hat{O}(n^ω) = O(n^{2.372})$ time \[Seidel '95\] providing significant savings over running $n$ SSSP instances separately. However, if one needs to compute multiple-source shortest paths (MSSP) from a set of $n^σ$ vertices, the previously best known running time was $\\hat{O}(\\min\\{n^ω, n^{2 + σ}\\})$: either compute APSP or run SSSP from each source. On the other hand, MSSP is only as hard as computing Boolean matrix product (BMM) between an $n^σ\\times n$ matrix and $n \\times n$ matrix, leaving a significant gap. Our first main result is an almost optimal algorithm for MSSP on undirected unweighted graphs running in $\\hat{O}(n^{ω(σ, 1, 1)})$ time, which gives a smooth interpolation between the SSSP and APSP algorithms. The main technical tool behind our result is a novel graph decomposition, which may be of independent interest. Next, we study the multiple-source reachability problem, where we need to determine whether a given set of $n^σ$ vertices can reach each of the vertices in a given directed graph. Multiple-source reachability can also be solved in $\\hat{O}(\\min\\{n^ω, n^{2 + σ}\\})$ time, with the same lower bound from rectangular BMM. We give an optimal algorithm that runs in $\\hat{O}(n^{ω(σ, 1, 1)})$ time, again matching the running time for BMM. Our algorithm for multiple-source reachability can be generalized to MSSP on DAGs. As an application, we provide an $O(n^{2.084})$ time algorithm for computing an $\\widetilde{O}(n)$-size shortcut set that reduces diameter to $O(n^{1/3})$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.