最大割問題

最大切割是切割，其尺寸至少是任何其他切割的尺寸。 在圖中找到最大切割的問題稱為最大切割問題。

問題可以簡單地說如下。 人們想要頂點集的子集S，使得S和互補子集之間的邊數儘可能大。

有一個更普遍的問題版本稱為加權Max-Cut。 在這個版本中，每個邊緣都有一個實數，它的重量，目標是最大化不是邊數，而是S和它的補數之間邊的總重量。 加權Max-Cut問題通常（但不總是）僅限於非負權重，因為負權重可以改變問題的性質。

基本介紹

• 中文名：最大割問題
• 外文名：Maximum cut problem

計算複雜性

在理論計算機科學中廣泛研究了與最大削減相關的以下決策問題：

給定圖G和整數k，確定G中是否存在至少k的切割大小。

已知該問題是NP完全的。很容易看出問題出在NP中：通過提供足夠大的切割，很容易證明是的答案。例如，可以通過從最大可滿足性（最大可滿足性問題的限制）的減少來顯示問題的NP完全性。[1]決策問題的加權版本是Karp的21個NP完全問題之一; [2] Karp通過減少分區問題顯示NP完全性。

上述決策問題的規範最佳化變體通常稱為最大割誤差或最大割誤差，定義為：

給定圖G，找到最大切割。

多項式時間算法

由於Max-Cut問題是NP-hard，因此在一般圖中沒有用於Max-Cut的多項式時間算法。

然而，在平面圖中，最大切割問題是路由檢查問題的雙重問題（找到最少訪問圖形的每個邊緣至少一次的最短遊覽的問題），在某種意義上，不屬於a的邊緣圖G的最大割集是在G的雙圖的最佳檢查巡視中加倍的邊的對偶。最佳檢查巡視形成自相交曲線，將平面分成兩個子集，子集曲線的匝數為偶數的點和匝數為奇數的子集;這兩個子集形成一個切口，其中包括在巡視中雙重出現奇數次數的所有邊。路線檢測問題可以在多項式時間內求解，這種對偶性允許最大切割問題也可以在平面圖的多項式時間內求解。然而，已知最大二分問題是NP難的。

近似算法

Max-Cut問題是APX-hard，意味著沒有多項式時間近似方案（PTAS），任意接近最優解，對於它，除非P = NP。因此，每個多項式時間近似算法實現嚴格小於1的近似比。

有一個簡單的隨機0.5近似算法：每個頂點翻轉一個硬幣來決定分配哪一半的分區。在期望中，一半的邊緣是切邊。該算法可以用條件機率的方法去隨機化;因此，還有一個簡單的確定性多項式時間0.5近似算法。一種這樣的算法以給定圖形的頂點的任意分區開始並且一次重複地移動一個頂點分區的一側到另一側，改進了每一步的解決方案，直到不再進行這種類型的改進。疊代次數最多為因為該算法在每個步驟中通過至少一個邊緣改善了切割。當算法終止時，入射到每個頂點的至少一半邊緣屬於切割，否則移動頂點將改善切割。因此，切割至少包括邊。

具有最佳已知近似比的Max-Cut的多項式時間近似算法是Goemans和Williamson使用半定規劃和隨機捨入的方法，其實現近似比，其中。如果唯一遊戲猜想為真，則這是最大切割的最佳可能近似比率。如果沒有這些未經證實的假設，已經證明NP難以逼近最大切割值，其近似比率優於。