1996 年， 美國計算機科學家 David R Karger 連同其他研究者在論文《 A new approach to the minimum cut problem》中提出了一個令人驚訝的隨機算法 Karger 算法，其在理論計算機科學中非常重要，尤其適用于大規模圖的近似最小割問題。

Karger 算法可以在時間為 O (m log^3n) 的圖中找到一個最小割點，他們將這個時間稱之為近線性時間，意思是線性乘以一個多對數因子。

在谷歌剛剛更新的一篇博客中，他們介紹了之前發布的一篇論文《 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 年開創性的給出了一個近乎線性的時間隨機算法，該算法能夠以較高的概率找到最小割，并且該工作還給出了一個關鍵見解，即存在一個更小的圖，它在很大程度上保留了所有割的大小。

這個發現是很有用的，因為可以使用較小的圖作為輸入來運行較慢的算法，并且較慢的運行時間（就較小的圖的大小而言）仍然可以與原始（較大）圖的大小接近線性。

事實上，關于最小割問題的許多結構發現都是沿著這個方向進行的。

谷歌是這樣做的，從具有 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 算法至關重要，并幫助谷歌得出了新算法。

最小割和 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 圖稀疏化的構造。

谷歌設計的新算法旨在構建一種劃分，來制定最小割的用例。與 Jason Li 在之前的工作中使用的更通用的現成方法相比，谷歌的這項研究更加精確、更加快捷。新研究在保證精度的同時在運行時間上也進行了優化，最終實現了針對最小割問題的近線性時間確定性算法。

本文轉自 機器之心 ，作者：機器之心

原文鏈接:??https://mp.weixin.qq.com/s/vmGmiYS5yqJUNkHysVIO1A??