摘要
多源可达性问题旨在计算从给定的源顶点子集可达的集合。对于 $n$-顶点有向图 $G=(V,E)$ 及源子集 $S \subseteq V$，其中 $|S|=n^{\sigma}$ 且 $\sigma \in [0,1]$，我们提出了一种近似最优的确定性算法，该算法在 $\tilde{O}(n^{\omega(\sigma)})$ 时间内解决该问题。这里，$\omega(\sigma)$ 是用于将一个 $n^{\sigma}\times n$ 矩阵与一个 $n \times n$ 矩阵相乘的矩形矩阵乘法指数。对于稠密图，这使得从最多 $n^{0.32}$ 个源进行可达性计算在近线性时间内完成，突破了超二次时间的限制，并且相较于 Elkin 和 Trehan 提出的最先进的 $n^{1+2/3\omega(\sigma)}$ 随机算法有了显著改进。
博主点评： 本文提出的算法在多源可达性问题上实现了时间复杂度的显著提升，特别是在处理稠密图的情况下，展示了矩阵乘法在图论中的强大应用。此研究为相关领域提供了新的思路，值得深入关注。