在图论中，从一小组顶点计算到整个图的距离和可达性是理论与实践中的重要基础任务。在无向无权图中，单源最短路径（SSSP）的计算在稠密图中需要 $O(n^2)$ 的时间，而全源最短路径（APSP）可以在 $\tilde{O}(n^{\omega}) = O(n^{2.372})$ 时间内完成，这比分别运行 $n$ 次 SSSP 显著节省时间。
然而，当需要从 $n^\sigma$ 个顶点计算多源最短路径（MSSP）时，已知的最佳运行时间为 $\tilde{O}(\min\{n^{\omega}, n^{2 + \sigma}\})$，即计算 APSP 或从每个源运行 SSSP。另一方面，MSSP 的计算难度与在 $n^\sigma \times n$ 矩阵与 $n \times n$ 矩阵之间进行布尔矩阵乘法（BMM）相当，存在显著差距。
我们的第一个主要结果是针对无向无权图的几乎最优的 MSSP 算法，其运行时间为 $\tilde{O}(n^{\omega(\sigma, 1, 1)})$，提供了 SSSP 和 APSP 算法之间的平滑插值。我们结果背后的主要技术工具是新颖的图分解，这可能具有独立的研究价值。
接下来，我们研究多源可达性问题，即确定给定的一组 $n^\sigma$ 个顶点是否能够到达给定有向图中的每个顶点。多源可达性问题同样可以在 $\tilde{O}(\min\{n^{\omega}, n^{2 + \sigma}\})$ 时间内解决，且与矩形 BMM 的下界相同。我们给出了一个最优算法，运行时间为 $\tilde{O}(n^{\omega(\sigma, 1, 1)})$，再次与 BMM 的运行时间相匹配。
我们的多源可达性算法可以推广到有向无环图（DAG）的 MSSP。作为应用，我们提供了一个 $O(n^{2.084})$ 时间的算法，用于计算一个大小为 $\tilde{O}(n)$ 的快捷集，从而将直径减少到 $O(n^{1/3})$。
博主点评： 该研究提出了针对多源最短路径和可达性问题的几乎最优算法，利用新颖的图分解技术，展示了理论与实际应用之间的紧密结合。这不仅优化了计算复杂度，还为后续研究提供了新的思路和方法。相较于传统方法，新的算法在处理大规模数据时具有显著优势。