二部圖中的最大加權獨立集合

Question

給定二部圖。每個頂點都有一些整數值 - 權重。

是否可以在多項式時間內在此圖中找到最大加權independent vertex set？

如果存在這樣的解決方案，這個問題的算法是什麼？

Answer 1

在任何圖中，獨立集的補碼是vertex cover，反之亦然，所以您的問題等同於在圖中查找最小權重頂點覆蓋。後者可以使用最大流量技術來解決：

引入超級源S和超級宿S，通過具有權重作爲容量的邊將兩部圖左側的節點連接到S。對右側和下沉做同樣的事情。爲原始圖的邊上分配無限容量。

現在在構建的網絡中找到最小的S-T切割。切割的值是最小頂點覆蓋的權重。要明白爲什麼這是真的，請考慮切邊：它們不能是原始邊緣，因爲它們具有無限的容量。如果切割左側邊緣，則這對應於將相應的左側節點放入頂點覆蓋物中。如果我們做而不是切割左側邊緣，我們需要切割右側相鄰頂點的所有右側邊緣。

因此，實際重構頂點覆蓋，只是收集所有彼此相鄰的頂點到切割的邊緣，或可替代地，左側節點不選自S到達和來自釀酒

到達右側節點

Answer 2

在我看來，這個問題似乎並不存在。首先，雙分圖已經由兩個獨立的集合組成。任何獨立的集合都必須是這些集合的子集，而對於正的權重，它們平凡必須具有較低的權重？

將一個二分圖劃分爲不連貫的子集也是微不足道的，而且對於大多數實際應用來說，一個二分圖將只有少數這些不連貫的子集，因此您可以將它們加起來。既然你可以在線性時間內找到所有獨立的子集，並且你可以在線性時間內找到它們的權重，那麼很明顯你可以在線性時間內在節點+邊上做到這一點，

這使我懷疑有人誤解了你的問題。

基本上，從您的雙向圖開始，選擇一個節點，找到所有連接到它的節點。如果這不是整個圖表，你找到了一個不連貫的子集，沖洗並重復。您可以隨時添加，因此整個思考需要對每個節點和邊的恆定時間操作= N + E中的線性時間。