我们为在 CONGEST 模型中近似稀疏切割值或图的导纳 (\phi) 提供了新的改进界限。我们的主要结果是提出了一种算法，其运行时间为 (O(\log^2 n / \phi)) 轮，其中每个顶点输出一个值 (\tilde \phi)，满足 (\phi \leq \tilde \phi \leq \sqrt{2.01\phi})。在大多数情况下，我们的算法显著优于先前最快的算法 [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]。此外，我们的结果还推广到 (k)-way 导纳。
我们通过近似归一化拉普拉斯矩阵的特征值来获得这些结果：[L = I - \text{Deg}^{-1/2}A\text{Deg}^{-1/2}]，其中 (A) 是邻接矩阵，Deg 是对角矩阵，包含加权度数。我们通过证明计算 (L) 的最小非平凡特征值的下界，显示我们的算法是近似最优的，即使在更强的 LOCAL 模型中。
之前的稀疏切割算法处于扩展器分解的技术领域，而我们的算法相对简单且易于实现。其核心依赖于著名的幂法，该方法归结为不断将拉普拉斯矩阵与向量相乘。这一操作可以在 CONGEST 模型中单轮完成。我们所有的算法适用于加权无向图，而我们的下界即使在无权图中也适用。
博主点评： 本文提出的算法通过简单而有效的特征值估计方法，显著提升了稀疏切割问题的计算效率，为图算法的发展提供了新的思路，尤其是在分布式环境下的应用潜力巨大。其与传统复杂算法相比，展现了更好的实用性与可实现性。