最大獨立集算法

Question

我不相信存在於比尋找所有可能的獨立集合中最大的蠻力方法以外的二分圖中發現的最大獨立頂點集的算法。

我想知道關於僞代碼來找到所有可能的頂點集。

說給出4個藍色頂點和4紅色二分圖。目前，我會

Start with an arbitrary blue, 
    find all red that don't match this blue 
    put all these red in Independent Set 
    find all blue that dont match these red 
    put these blue in Independent Set 
    Repeat for next vertex in blue 

Repeat all over again for all blue then all vertices in red. 

據我所知，這種方式並沒有給我的所有可能的獨立設置的組合可言，因爲第一步後，我選擇所有的不匹配，而不是通過每步進的下一個顏色頂點方法可行。

例如，給定的圖形與匹配

B R 
1 1 
1 3 
2 1 
2 3 
3 1 
3 3 
4 2 
4 4 

Start with blue 1 
    Choose red 2 and 4 since they dont match 
    Add 2, 4 to independent Set 
    Choose 2 and 3 from blue since they dont with 2 or 4 from red 
    Add 2 and 3 from blue to independent set as well. 
Independent Set = 1,2,3 from blue 2,4 from red 
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set) 

有沒有一種方法，我可以改善這種算法爲所有可能更好的搜索。我知道|雙極圖|最大集| = | Red | + |藍色| - |最大匹配|。

問題出現與通過選擇在第一次去的所有可能的紅色爲一個給定的藍色，如果這些紅色連接到所有其他可能的藍色，然後我一套永遠只擁有全部爲1米的藍色和紅色休息的可能性。

Answer 1

我不相信有一種算法找到最大的獨立頂點集在二分圖中，而不是在所有可能的獨立集中找到最大值的蠻力方法。

有：找到最大獨立集是等價於求的最小頂點覆蓋（通過取結果的補碼），和Konig's theorem指出，在二分圖最小頂點覆蓋相當於最大匹配，而且該可以在多項式時間中找到。我不知道如何找到所有的配對，但似乎可以指數多。

Answer 2

亞倫McDaid提到他現在刪除了答案，問題找到一個最大獨立集就相當於找到最大團。等價的是，在圖G中找到最大獨立集與在G的補集中找到最大集相同。這個問題被稱爲NP完全。

你提到的蠻力解決方案採用O(n^2 2^n)，但你可以做得比這更好。 Robson有一篇題爲「1986年最大獨立集的算法」的文章，它給出了一個算法，該算法需要0<c<1（我相信c約爲1/4，但我可能會誤）。 。

有一點要注意，如果你有一個二分圖是兩側形成獨立的組，在完成二分圖K_{b,r}被分隔B x R與|B|=b和|R|=r那裏是從每一個頂點B邊緣的每一個頂點在R中且沒有在B之內，也沒有在R之內，最大獨立集合爲B if b>=r，否則爲R。

以B或R一般不會工作。sdcvvc注意到頂點{1,2,3,A,B,C}和邊緣{A,1}, {A,2}, {A,3}, {B,3}, {C,3}的例子。在這種情況下，最大獨立集是{1,2,B,C}，它大於分區{A,B,C}或{1,2,3}。

它可能會改善Robson的算法，以B或R中的較大值開始，並從那裏開始，但我不確定這會產生多大的差異。

或者，您可以使用圖的二部分補碼上的Hopcroft–Karp algorithm來查找最大匹配，然後將匹配中使用的頂點作爲獨立集。這給出了一個多項式時間算法來解決這個問題。