google博客放出新研讨，求解无向图的最小割成绩。
1996 年， 美国计算机科学家 David R Karger 连同其他研讨者在论文《 A new approach to the minimum cut problem》中提出了一个令人惊讶的随机算法 Karger 算法，其在理论计算机科学中非常重要，尤其适用于大规模图的近似最小割成绩。
Karger 算法可以在时光为 O (m log^3n) 的图中找到一个最小割点，他们将这个时光称之为近线性时光，意思是线性乘以一个多对数因子。
在google刚刚更新的一篇博客中，他们介绍了之前发布的一篇论文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》，研讨获得了 ACM-SIAM SODA24 最佳论文奖。文章详细阐述了一个几乎是线性时光内（而不是近线性时光）运行的新算法，这个算法是确定性的，能够可靠地找到准确的最小割，改进了之前可能无法保证结果准确或只适用于单一图的算法。可以说这是自 Karger 著名的随机化算法以来的重大发现。
论文地址：https://arxiv.org/pdf/2401.05627.pdf
论文标题：Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
注：最小割成绩（通常称为最小割）是关于图连通性的基本结构成绩，它一般关注的是断开网络最单一的方式是什么？在图论中，去掉其中整个边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割，一张图上最小的割称为最小割。
一张图及其两个割：红色点线标出了一个包孕三条边的割，绿色划线则表示了这张图的一个最小割（包孕两条边）。
方式介绍
关于最小割成绩，Karger 在 1996 年开创性的给出了一个近乎线性的时光随机算法，该算法能够以较高的几率找到最小割，并且该工作还给出了一个关键见解，即存在一个更小的图，它在很大程度上保留了整个割的巨细。
这个发现是很有用的，因为可以使用较小的图作为输入来运行较慢的算法，并且较慢的运行时光（就较小的图的巨细而言）仍然可以与原始（较大）图的巨细接近线性。
事实上，关于最小割成绩的许多结构发现都是沿着这个方向进行的。
google是这样做的，从具有 n 个节点的图 G 开始，然后依据论文《 Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs 》（作者为 Benzur、Karger）提出的割保留稀薄化方式，证明了可以机关一个边数更少的稀薄加权图 G'，且在这个图上，几乎整个割的巨细与原图 G 中相应割的巨细大致相同。
这个概念可以通过以下例子来说明：原始图由两个通过单一边对接的完全图组成，而稀薄化后的图边数更少，但边的权重更大，同时整个割的巨细大致得以保留。
为了构建这种较稀薄的图，Benzur 和 Karger 采用了独立采样边的方式。在这种方式中，图 G 中的每条边都有一定几率被包孕在图 G' 中，并且其在 G' 中的权重会根据采样几率的倒数进行放大（例如，如果一条原权重为 1 的边以 10% 的几率被包孕，则其权重调整为 10）。结果表明，这种非常单一（几乎是线性时光）的方式具有很高的成功几率，可以构建出保持割的图稀薄化。
然而，Karger 算法是一种蒙特卡洛算法，即输出可能小几率不准确，并且除了与实际已知的最小割进行比较之外，没有已知的方式可以判断输出是否准确。
因此，研讨人员一直在努力探索解决近线性时光确定性算法开放成绩的方式。由于 cut-preserving 图稀薄化的机关是 Karger 算法中唯一随机的组成部分，因此一种方式是在近线性时光内找到稀薄化的确定性机关（也称为去随机化）。
2015 年，Kawarabayashi 和 Thorup 实现了一个重要的里程碑 —— 找到针对单一图（即每对节点之间至多有一条边且整个边权重等于 1 的图）的确定性近线性时光算法。
该研讨得出一个关键思路，即最小割和另一个重要的图结构（称为「low-conductance cut」）之间存在一些联系。这种联系对于后来在一般边权重图上去随机化 Karger 算法至关重要，并帮助google得出了新算法。
最小割和 low-conductance cut 的对齐
图割 S 的 conductance 定义为 S 的 cut 巨细与 S 的 volume 之比（假设 S 是切口的较小体积侧且非空），其中 S 的 volume 是 S 中节点的度数。
low-conductance 的 cut S 直观地捕获了网络中的瓶颈，因为只有少量边（相对于其 volume）将 S 对接到图的其余部分。图的 conductance 被定义为图中任何 cut 的最小 conductance，并且大 conductance 的图（也称为扩展图）被认为是良好对接的，因为内部没有瓶颈。
红色虚线表示 cut 巨细为 2，较小的一侧（底部）volume 为 24，因此其 conductance 为 1/12，这也是图的 conductance。
Kawayabarashi 和 Thorup 观看到，在最小节点度数较大的单一图中，任何非平庸（即两侧至少有两个节点）最小割都必须具有 low conductance。根据这一观看，如果可以将图分别为对接良好的簇（cluster），则分别必须与每个非平庸最小割一致，因为每个簇必须完全位于每个 cut 的一侧。然后，将每个簇收缩为一个节点，并处理较小的图，其中原始图的整个非平庸最小割都完好无损。
然而，对于加权图，上述观看不再成立，并且单一图情况中使用的相同分别可能与非平庸最小割不完全一致。
如下图所示，Jason Li 2021 年观看到，这种分别仍然与非平庸最小割大致一致。特别地，对于非平庸最小割 S，存在与 S 相差不大的 cut S'，使得 S' 与簇一致。Jason Li 进一步观看到，可以利用分别的这种特性来有效地去随机化 cut-preserving 图稀薄化的机关。
google设计的新算法旨在构建一种分别，来制定最小割的用例。与 Jason Li 在之前的工作中使用的更通用的现成方式相比，google的这项研讨更加精确、更加快捷。新研讨在保证精度的同时在运行时光上也进行了优化，最终实现了针对最小割成绩的近线性时光确定性算法。
参考链接：https://research.google/blog/solving-the-minimum-cut-problem-for-undirected-graphs/