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

Karger 算法可以在時(shí)間為 O (m log^3n) 的圖中找到一個(gè)最小割點(diǎn)，他們將這個(gè)時(shí)間稱(chēng)之為近線(xiàn)性時(shí)間，意思是線(xiàn)性乘以一個(gè)多對(duì)數(shù)因子。

在谷歌剛剛更新的一篇博客中，他們介紹了之前發(fā)布的一篇論文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》，研究獲得了 ACM-SIAM SODA24 最佳論文獎(jiǎng)。文章詳細(xì)闡述了一個(gè)幾乎是線(xiàn)性時(shí)間內(nèi)（而不是近線(xiàn)性時(shí)間）運(yùn)行的新算法，這個(gè)算法是確定性的，能夠可靠地找到正確的最小割，改進(jìn)了之前可能無(wú)法保證結(jié)果正確或只適用于簡(jiǎn)單圖的算法。可以說(shuō)這是自 Karger 著名的隨機(jī)化算法以來(lái)的重大發(fā)現(xiàn)。

• 論文地址：https://arxiv.org/pdf/2401.05627.pdf
• 論文標(biāo)題：Deterministic Near-Linear Time Minimum Cut in Weighted Graphs?

注：最小割問(wèn)題（通常稱(chēng)為最小割）是關(guān)于圖連通性的基本結(jié)構(gòu)問(wèn)題，它一般關(guān)注的是斷開(kāi)網(wǎng)絡(luò)最簡(jiǎn)單的方法是什么？在圖論中，去掉其中所有邊能使一張網(wǎng)絡(luò)流圖不再連通（即分成兩個(gè)子圖）的邊集稱(chēng)為圖的割，一張圖上最小的割稱(chēng)為最小割。

一張圖及其兩個(gè)割：紅色點(diǎn)線(xiàn)標(biāo)出了一個(gè)包含三條邊的割，綠色劃線(xiàn)則表示了這張圖的一個(gè)最小割（包含兩條邊）。

方法介紹

關(guān)于最小割問(wèn)題，Karger 在 1996 年開(kāi)創(chuàng)性的給出了一個(gè)近乎線(xiàn)性的時(shí)間隨機(jī)算法，該算法能夠以較高的概率找到最小割，并且該工作還給出了一個(gè)關(guān)鍵見(jiàn)解，即存在一個(gè)更小的圖，它在很大程度上保留了所有割的大小。

這個(gè)發(fā)現(xiàn)是很有用的，因?yàn)榭梢允褂幂^小的圖作為輸入來(lái)運(yùn)行較慢的算法，并且較慢的運(yùn)行時(shí)間（就較小的圖的大小而言）仍然可以與原始（較大）圖的大小接近線(xiàn)性。

事實(shí)上，關(guān)于最小割問(wèn)題的許多結(jié)構(gòu)發(fā)現(xiàn)都是沿著這個(gè)方向進(jìn)行的。

谷歌是這樣做的，從具有 n 個(gè)節(jié)點(diǎn)的圖 G 開(kāi)始，然后依據(jù)論文《 Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs 》（作者為 Benzur、Karger）提出的割保留稀疏化方法，證明了可以構(gòu)造一個(gè)邊數(shù)更少的稀疏加權(quán)圖 G'，且在這個(gè)圖上，幾乎所有割的大小與原圖 G 中相應(yīng)割的大小大致相同。

這個(gè)概念可以通過(guò)以下例子來(lái)說(shuō)明：原始圖由兩個(gè)通過(guò)單一邊連接的完全圖組成，而稀疏化后的圖邊數(shù)更少，但邊的權(quán)重更大，同時(shí)所有割的大小大致得以保留。

為了構(gòu)建這種較稀疏的圖，Benzur 和 Karger 采用了獨(dú)立采樣邊的方法。在這種方法中，圖 G 中的每條邊都有一定概率被包含在圖 G' 中，并且其在 G' 中的權(quán)重會(huì)根據(jù)采樣概率的倒數(shù)進(jìn)行放大（例如，如果一條原權(quán)重為 1 的邊以 10% 的概率被包含，則其權(quán)重調(diào)整為 10）。結(jié)果表明，這種非常簡(jiǎn)單（幾乎是線(xiàn)性時(shí)間）的方法具有很高的成功概率，可以構(gòu)建出保持割的圖稀疏化。

然而，Karger 算法是一種蒙特卡洛算法，即輸出可能小概率不正確，并且除了與實(shí)際已知的最小割進(jìn)行比較之外，沒(méi)有已知的方法可以判斷輸出是否正確。

因此，研究人員一直在努力探索解決近線(xiàn)性時(shí)間確定性算法開(kāi)放問(wèn)題的方法。由于 cut-preserving 圖稀疏化的構(gòu)造是 Karger 算法中唯一隨機(jī)的組成部分，因此一種方法是在近線(xiàn)性時(shí)間內(nèi)找到稀疏化的確定性構(gòu)造（也稱(chēng)為去隨機(jī)化）。

2015 年，Kawarabayashi 和 Thorup 實(shí)現(xiàn)了一個(gè)重要的里程碑 —— 找到針對(duì)簡(jiǎn)單圖（即每對(duì)節(jié)點(diǎn)之間至多有一條邊且所有邊權(quán)重等于 1 的圖）的確定性近線(xiàn)性時(shí)間算法。

該研究得出一個(gè)關(guān)鍵思路，即最小割和另一個(gè)重要的圖結(jié)構(gòu)（稱(chēng)為「low-conductance cut」）之間存在一些聯(lián)系。這種聯(lián)系對(duì)于后來(lái)在一般邊權(quán)重圖上去隨機(jī)化 Karger 算法至關(guān)重要，并幫助谷歌得出了新算法。

最小割和 low-conductance cut 的對(duì)齊

圖割 S 的 conductance 定義為 S 的 cut 大小與 S 的 volume 之比（假設(shè) S 是切口的較小體積側(cè)且非空），其中 S 的 volume 是 S 中節(jié)點(diǎn)的度數(shù)。

low-conductance 的 cut S 直觀(guān)地捕獲了網(wǎng)絡(luò)中的瓶頸，因?yàn)橹挥猩倭窟叄ㄏ鄬?duì)于其 volume）將 S 連接到圖的其余部分。圖的 conductance 被定義為圖中任何 cut 的最小 conductance，并且大 conductance 的圖（也稱(chēng)為擴(kuò)展圖）被認(rèn)為是良好連接的，因?yàn)閮?nèi)部沒(méi)有瓶頸。

紅色虛線(xiàn)表示 cut 大小為 2，較小的一側(cè)（底部）volume 為 24，因此其 conductance 為 1/12，這也是圖的 conductance。

Kawayabarashi 和 Thorup 觀(guān)察到，在最小節(jié)點(diǎn)度數(shù)較大的簡(jiǎn)單圖中，任何非平凡（即兩側(cè)至少有兩個(gè)節(jié)點(diǎn)）最小割都必須具有 low conductance。根據(jù)這一觀(guān)察，如果可以將圖劃分為連接良好的簇（cluster），則劃分必須與每個(gè)非平凡最小割一致，因?yàn)槊總€(gè)簇必須完全位于每個(gè) cut 的一側(cè)。然后，將每個(gè)簇收縮為一個(gè)節(jié)點(diǎn)，并處理較小的圖，其中原始圖的所有非平凡最小割都完好無(wú)損。

然而，對(duì)于加權(quán)圖，上述觀(guān)察不再成立，并且簡(jiǎn)單圖情況中使用的相同劃分可能與非平凡最小割不完全一致。

如下圖所示，Jason Li 2021 年觀(guān)察到，這種劃分仍然與非平凡最小割大致一致。特別地，對(duì)于非平凡最小割 S，存在與 S 相差不大的 cut S'，使得 S' 與簇一致。Jason Li 進(jìn)一步觀(guān)察到，可以利用劃分的這種特性來(lái)有效地去隨機(jī)化 cut-preserving 圖稀疏化的構(gòu)造。

谷歌設(shè)計(jì)的新算法旨在構(gòu)建一種劃分，來(lái)制定最小割的用例。與 Jason Li 在之前的工作中使用的更通用的現(xiàn)成方法相比，谷歌的這項(xiàng)研究更加精確、更加快捷。新研究在保證精度的同時(shí)在運(yùn)行時(shí)間上也進(jìn)行了優(yōu)化，最終實(shí)現(xiàn)了針對(duì)最小割問(wèn)題的近線(xiàn)性時(shí)間確定性算法。

本文轉(zhuǎn)自 機(jī)器之心 ，作者：機(jī)器之心

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