如何找到價帶約束的二分圖最大子圖？

Question

我有一個雙向圖。我將引用相應不相交集合的紅色節點和黑色節點。

我想知道如何找到一個連接誘導子最大化的紅色節點，同時確保在所有子黑色結點有新價小於或等於二，「誘導」裝置的數量如果兩個節點連接在原始圖中並且都存在於子圖中，那麼它們之間的邊將自動包含在內。最後我想介紹一下非負邊緣權重。

這可以歸結爲標準圖算法嗎？希望有一個已知的複雜性和簡單的實施。

貪婪地生長子圖顯然是可能的。但這是最好的嗎？

Answer 1

我敢肯定，這個問題屬於NP-complete class，所以沒有簡單的方法來解決它。我建議你使用constraint satisfaction的方法。有很多方法可以解決您的問題，例如混合整數編程，MaxSAT甚至pseudo-boolean constraints。

對於第一次嘗試，我會推薦MiniZinc求解器。例如，請考慮this在MiniZinc中定義和解決圖形問題的示例。

Answer 2

不幸的是，這是NP難，所以可能沒有多項式時間算法來解決它。這裏是從NP難問題Independent Set中減去，其中給出了圖G =（V，E）（其中n = | V |和m = | E |）和整數k，並且任務是確定是否有可能找到一組k或更多個頂點，使得該組中沒有兩個頂點通過邊相連的：

• 對於G中每個頂點V_I，在H.
創建一個紅色頂點R_I
• 對於G中每個邊沿（V_I，v_j），創建H中執行以下操作：
  • 黑色頂點b_ij，
  • n + 1個紅色頂點t_ijk（1 < = K < = N + 1），
  • 黑-N頂點u_ijk（1 < = K < = N），
  • n條邊（t_ijk，u_ijk）（1 < = K < = N）
  • Ñ （r_i，b_ij），（r_j，b_ij）和（t_ij1，b_ij）的邊緣（t_ijk，u_ij {k-1}）（2 < = k < = n + 1）
  • 。
• 對於每對頂點V_I，v_j，創建以下的：
  • 黑色頂點c_ij，
  • 兩個邊緣（R_I，c_ij）和（r_j，c_ij）。
• 將閾值設置爲m（n + 1）+ k。

調用所有r_i R的集合，所有b_ij B的集合，所有c_ij C的集合，所有t_ij T的集合以及所有u_ij U的集合。

這裏的一般想法是，我們迫使每個黑色頂點b_ij至少在對應於G中邊緣（i，j）的端點的2個紅色頂點r_i和r_j中選擇一個。我們通過給定每個這些b_ij頂點3個輸出邊緣，其中一個（一個到t_ij1）是「必須擁有的」 - 也就是說，任何其中t_ij1頂點是而非選定的解決方案都可以通過選擇它來改進，如以及它連接到的其他n個紅色頂點（通過在t_ijk中的頂點和u_ijk中的頂點之間交替的「擺動路徑」），除去r_i或r_j以恢復沒有黑色頂點具有3個或更多鄰居的屬性必要時提供解決方案，然後根據需要通過從C中選擇頂點來最終恢復連通性。 （c_ij頂點是「連接符」：它們的存在只是爲了確保我們包含的任何子集都可以被製作爲單個連接組件。）

首先假設G中存在大小爲k的IS。證明在H中至少存在m（n + 1）+ k個紅色節點的連通感應子圖X，其中每個黑色頂點在X中至多有2個鄰居。

首先，在X中包含k個頂點從R對應於IS中的頂點（這樣的集合必須通過假設存在）。因爲這些頂點形成一個IS，所以B中沒有頂點與它們中的多於1個相鄰，所以對於每個頂點b_ij，我們可以安全地添加它，並且將從t_ij1開始的2n + 1個頂點的「擺動路徑」好。每個這些擺動路徑都包含n + 1個紅色頂點，並且有m個這樣的路徑（G中每個邊都有一個），所以現在在X中有m個（n + 1）+ k個紅色頂點。最後，爲了確保X是連接的，每一個頂點c_ij都加上它使得r_i和r_j都已經在X中：注意，這並不改變X中紅色頂點的總數。

現在假設有一個連接的感應子圖X H中至少有m（n + 1）+ k個紅色節點，其中每個黑色頂點在X中至多有2個鄰居。我們將證明G中有一個大小爲k的IS。

H中唯一的紅色頂點是R中的那些頂點和T中的頂點.R中只有n個頂點，所以如果X不包含所有m個浮動路徑，它必須至多有（m-1）（n +1）+ n = m（n + 1）-1紅色頂點，這與假設它至少有m（n + 1）+ k個紅色頂點相矛盾。因此X必須包含所有m個假髮路徑。這在X中留下了k個其他紅色頂點，它們必須來自R.這些頂點中沒有兩個頂點可以與B中的同一個頂點相鄰，因爲該B頂點將與3個頂點相鄰：因此，這些頂點對應於G中的一個IS

由於IS的YES實例意味着您的問題的構造實例的YES實例，反之亦然，所以問題的構造實例的解決方案完全對應於IS實例的解決方案;並且由於構造顯然是多項式時間的，這表明你的問題是NP難的。