{"id":"arxiv:2606.26554","kind":"preprint","title":"Almost Optimal Multiple Source Shortest Paths and Reachability","authors":["Barna Saha","Yinzhan Xu","Christopher Ye"],"author_count":3,"year":2026,"published":"2026-06-25","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2606.26554","nct_id":null,"source_url":"https://arxiv.org/abs/2606.26554","archive_url":"https://space-kitty.com/papers/arxiv:2606.26554","updated":"2026-06-25","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2606.26554","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}