如何找到定向圖的最大無環子圖的2-近似解？

如何找到沒有定向圖的週期來確定最大子圖的問題的2-近似解？如果子圖包含具有相同屬性的其他圖中的最大邊數，則子圖是「最大值」。如何找到定向圖的最大無環子圖的2-近似解？

2-近似意味着我們可以構建比最優圖小2倍的圖。這是一個相當大的約束減少，應該導致相當愚蠢的算法 - 哇！ - 事實證明，它只比精確的解決方案差兩倍。

[這是我最近通過的考試中的一個問題。不再是作業了。]

來源

2009-12-22 Pavel Shved

將節點集合分成兩個非空集合A和B.考慮從A到B的邊集合和從B到A的邊集合。從較小的邊中拋出邊設置並保留較大集合的邊緣（任意打斷關係）。分別在A和B上遞歸。

由此產生的圖是非循環的，因爲每次循環都會在循環的節點第一次被分割到A和B之間時被打破。我們拋出的全部邊集不會大於我們保留的全部邊集，所以我們最多拋出一半的邊緣。

[注：我不認爲你的意思是'最大'在這裏，你的意思是'最大'。「最大」圖通常意味着沒有符合條件的正確超集。一個最大的非循環子圖很容易構造，沒有近似因子，只需要將所有邊添加到一個新圖中，只要它們不添加循環。]

來源

2009-12-22 06:38:40

似乎是一個正確的O（V²）解決方案。謝謝你的語言解釋。 –

它可以在O（E）時間完成。令A爲{v_1}，B爲{v_2，... v_n}。你只需要比較v_1的indegree和outdegree並以較小的程度放棄邊緣。針對A = {v_2}和B = {v_3，...，v_n}重複以下步驟，比較忽略與v_1 /從v_1邊緣的v_2的indegree/outdegree。 –

爲什麼我們不能在圖上運行DFS，將每條邊標記爲前沿或後沿，然後將所有前沿作爲我們的結果？ –

Vijay Vazirani的關於近似算法的書有這樣的第一個練習問題，他給出了一個非常明顯的暗示，我將在這裏重述。

任意編號從1到n的節點;
將邊緣分成兩組，前後向（無交叉邊緣）;
選擇正向組和後向組之間的較大組。

正確性和近似比率證明都是微不足道的。

編輯：其實@Keith蘭德爾的解決方案只是一個變種，其中他編號的集合中的節點從1到| A |以及來自| A |的B中的節點+ 1到| A | + | B |，對於遞歸情況也是如此。

來源

2016-03-07 18:00:36

如何找到定向圖的最大無環子圖的2-近似解？

回答

相關問題