查找帶有非常重要頂點的二分圖頂點覆蓋

Question

我知道，通過首先找到最大匹配，然後使用Konig's Theorem將此匹配變成相同順序的頂點覆蓋，我可以找到二分圖的最小頂點覆蓋。

但是，獲得的結果只是可能有多個有效頂點覆蓋的結果之一。在下面的圖中，{A，B}，{C，D}和{B，C}都是有效的封面。應用Konig方法產生{A，B}的覆蓋。

(A)=====(C) 
    /
    /
/
(B)=====(D) 

如何檢查包含給定重要頂點（如頂點D）的最小頂點覆蓋的存在？

我的第一個猜測是翻轉該圖並找到另一個最小頂點覆蓋。在上述情況下，這將產生{C，D}。如果兩個解都不包含重要的頂點，那麼它不是最小覆蓋的一部分。但是，我還沒有深入到足以真正證明這一點。

Answer 1

我建議以下方法

1. 找出最小頂點覆蓋的大小（讓一個頂點覆蓋是$ C $）
2. 刪除「非常重要頂點」和所有的邊所涵蓋相同的（頂點是$ V $）
3. 重複此過程，並讓新的頂點覆蓋是$ C '$

如果$ | C' + V | = | C | $然後報告最小頂點覆蓋else報告沒有給定頂點存在最小頂點覆蓋。

我想你有同樣的答案，證明也是沿着相同的路線。

新頂點覆蓋不能更小，因爲它違反了$ C $是最小頂點覆蓋之一的條件。

另外$ C'$是涵蓋圖的其餘部分的最小覆蓋。

如果至少有一個包含頂點$ V $的最小頂點覆蓋，那麼該集合中的其餘頂點將覆蓋除與$ V $相鄰的頂點之外的所有頂點，但這意味着$ | C '| $不大於$ | C | -1 $，因此如果不這樣做，就意味着沒有包含VIP邊的最小頂點覆蓋。

Answer 2

使用匈牙利算法計算初始匹配，給出在該頂點結束的所有邊的權重較低。