這是NP優化嗎？

在完整的Ñ -partite無向圖中，每個三方組具有Ñ頂點。我的問題是要在圖表中找到最小重量的n -clique。我想知道這個問題是否可以在Poly-n時間內解決。這是NP優化嗎？

更多細節的術語：

完整的k分圖：其中頂點相鄰的曲線圖，當且僅當它們屬於不同的部集（wikipedia）。圖中有k個分組集。在我的問題中，k = n。

Clique：圖G中的集團是G的完整子圖;也就是說，它是頂點的子集S，使得S中的每兩個頂點都通過G中的邊連接（wikipedia）。

Min-weight Clique：圖中的每條邊都有一個權重。集團的重量是集團中所有邊的權重的總和。目標是找到一個最小重量的派系。

請注意，所需團體的大小爲n，它是完整n-partite圖中最大的團體大小，並且始終可以實現。

我已經搜索了幾個小時，似乎沒有研究解決的具體問題。有什麼建議麼？

來源

2013-07-07 linusz

我們知道集團是什麼。你是否告訴我們你想優化[NP難題]（http://en.wikipedia.org/wiki/Clique_problem）^ _ ^？ –

@BenjaminGruenbaum嗯，我想這不同於鏈接中的派系問題。我希望這種差異可能會導致一些快速解決方案。 – linusz

首先有n ** k個選項可以檢查（一個派系只在圖形不同部分的邊緣之間）。只需檢查所有選項，檢查一個部分中的每個節點（n個）與其他部分中的節點，選擇節點的所有選項都是n，您對k個部分進行選擇，因此您有n^k個運行時間（就像你想的那樣）......儘管如此，它仍然非常緩慢。 –

是的，這是NP難通過從CLIQUE這種減少。

設（G，K）是集團的實例（確定是否存在基數至少k的集團）。準備一個具有K中每個頂點的k個副本和兩個頂點v和w之間的邊的k-部分圖H，當且僅當它們在不同部分中，並且它們是G中相鄰頂點的副本。在G中存在一個k-clique當且僅當H中存在一個k-集團（有權重時：使現有的邊權重爲1，並引入缺失的權重爲0.）

（當然這是在文獻中，但它是星期天，並且我不喜歡看。）

來源

2013-07-07 18:41:43

我不確定減少。我的問題是最小化團體的重量，並且團體大小已知是最大的，即，n（它總是可以在完整的n分圖中獲得）。另外，在你構造的圖H中，同一頂點副本的頂點不連接（它們不相鄰）。但在我的情況中並非如此：任何屬於不同分區的兩個頂點都已連接。 – linusz

@linusz您感興趣的問題的加權版本的減少有一個完整的k-分圖，如果邊連接G鄰接頂點的不同部分中的副本，則邊具有權重0，否則爲1。 –

二次分配可以通過每個相關聯二分集的位置，並與各二分集的每個頂點的設施很容易降低到這個問題。與同一設施關聯的兩個頂點之間的任何邊的權重設置爲無窮大。由於二次分配是NP難的，所以這個問題也是NP難的。

來源

2013-07-07 20:02:33

這是NP優化嗎？

回答

相關問題