簡單圖| V | = 10^6，度4：最大獨立子集？

給出一個含有100萬個頂點的最大度數爲4的簡單圖。簡單圖| V | = 10^6，度4：最大獨立子集？

我們想要查找最大獨立子集。

在一般情況下，它是NP難。

度數是4的事實提供了一個有效的解決方案來計算它嗎？

來源

2012-08-02 Andrew Tomazos

您的意思是？ http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 – 2012-08-02 16:57:09

@ DennisMeng：是的，謝謝，我已經更新了這個問題以使用正確的術語。 – 2012-08-02 17:02:25

進一步讀入，維基百科頁面，我發現這個關於這個問題：

例如，對於稀疏圖（圖中的邊緣的數量是最多的恆定倍數的頂點數量任何子圖），最大集團有界限大小，並可能發現完全線性時間;然而，對於相同類別的圖表，或者甚至對於更受限類別的有界度圖，尋找最大獨立集合是MAXSNP完全的，這意味着，對於某些常數c（取決於度），難以找到一個近似解決方案，它的最優解是c的一個因子。 ^[7]

你的情況是有限度的情況下，所以從這個片段來看，你更嚴格的版本仍然是NP難。

來源

2012-08-02 17:09:19

這是因爲圖中的最大獨立集相當於圖的補充中的最大集團（圖中具有剛好從第一圖中缺失的邊的集合）。如果一個是有界的，另一個不是。 – chepner 2012-08-02 20:21:57

參考文獻[5]可以通過谷歌搜索找到，它顯示獨立集已經是3次圖的完整的MAXSNP。 – sdcvvc 2012-08-06 17:17:49

有一個非常簡單的貪婪1/5逼近。取任何頂點，將其添加到獨立集，並從圖中移除鄰居。繼續，直到沒有頂點。這個技巧更通用的版本是Turan's theorem。

來源

2012-08-06 17:16:15 sdcvvc

如果您在維基百科頁上閱讀，它引用了一個參考文獻，說如果您選擇最低-degree頂點而不是隻是一個任意的頂點，你會得到2的因子。 – 2012-08-06 21:34:00

簡單圖| V | = 10^6，度4：最大獨立子集？

回答

相關問題