頂點蓋

在圖理論中，圖的頂點蓋（有時是節點蓋）是一組頂點，其中包括圖形每個邊緣的至少一個端點。

在計算機科學中，找到最小頂點覆蓋的問題是經典優化問題。它是np-hard ，因此如果p≠np，則無法通過多項式時間算法求解。此外，很難近似- 如果唯一的遊戲猜想是正確的，則不能將其近似於小於2的因素。另一方面，它具有幾個簡單的2因子近似值。它是具有近似算法的NP-硬優化問題的典型示例。它的決策版本，即頂點覆蓋問題，是KARP的21個NP完整問題之一，因此是計算複雜性理論中經典的NP完整問題。此外，頂點覆蓋問題是固定參數可處理的，並且是參數化複雜性理論的中心問題。

最小頂點覆蓋問題可以作為半綜合的線性程序提出，其雙線性程序是最大匹配問題。

頂點覆蓋問題已被推廣到超圖，請參見HyperGraphs中的頂點覆蓋物。

定義

正式，頂點蓋無向圖是這樣 ，也就是說這是一組頂點每個邊緣在頂點蓋上至少具有一個端點的地方 。據說這樣的一套涵蓋了 。上圖顯示了兩個頂點蓋的示例，帶有一些頂點蓋標記為紅色。

最小頂點蓋是最小尺寸的頂點蓋。頂點蓋號碼是最小頂點蓋的大小，即 。下圖顯示了前圖中最小頂點覆蓋的示例。

例子

• 所有頂點的集合都是頂點蓋。
• 任何最大匹配的端點形成頂點蓋。
• 完整的兩分圖具有最小的頂點覆蓋尺寸 。

特性

• 當且僅當其補充是獨立集時，一組頂點是頂點蓋。
• 因此，圖的頂點的數量等於其最小頂點覆蓋號碼以及最大獨立集的大小。

計算問題

最小頂點覆蓋問題是在給定圖中找到最小的頂點蓋的優化問題。

實例：圖形

輸出：最小的數字這樣具有大小的頂點蓋 。

如果將問題稱為決策問題，則稱為頂點覆蓋問題：

實例：圖形和積極的整數 。

問題：做最多有大小的頂點覆蓋 ？

頂點覆蓋問題是NP完整的問題：這是KARP的21個NP完整問題之一。它通常在計算複雜性理論中用作NP硬度證明的起點。

ILP公式

假設每個頂點的相關成本為 。 （加權）最小頂點覆蓋問題可以作為以下整數線性程序（ILP）提出。

最小化				（最小化總成本）
約束		對全部		（覆蓋圖的每個邊緣），
		對全部 。		（每個頂點都在頂點蓋中）

該ILP屬於涵蓋問題的更通用的ILP類別。這個ILP的完整性差距是 ，因此其放鬆（允許每個變量在0到1的間隔中，而不是要求變量僅為0或1）給出一個因子 - 最小頂點覆蓋問題的近似算法。此外，該ILP的線性編程放鬆是半綜合的，也就是說，每個條目都有一個最佳解決方案是0、1/2或1。可以通過選擇變量為非零的頂點的子集，從該分數解決方案中獲得2個值的頂點蓋。

確切的評估

頂點覆蓋問題的決策變體是NP完整的，這意味著不太可能有一個有效的算法來求解它以解決任意圖。 NP完整性可以通過從3個可滿足性中降低或像KARP所做的那樣來證明，通過減少集團問題。即使在三次圖中，最多也是在平面圖中，頂點蓋仍然保持NP完整。

對於兩分圖，頂點蓋與Kőnig定理所描述的最大匹配之間的等效性允許在多項式時間內解決兩部分頂點覆蓋問題。

對於樹的圖，算法通過在樹上找到第一片葉並將其父添加到最小頂點蓋中，從而在多項式時間找到最小的頂點覆蓋物，然後刪除葉子和父母，並持續不斷，直到沒有邊緣一直保持邊緣一直保持不變。那個樹。

固定參數障礙性

詳盡的搜索算法可以在時間2 ^k n ^{o （1）}中解決問題，其中k是頂點蓋的大小。因此，頂點蓋是固定參數可進行的，如果我們只對小k感興趣，我們可以在多項式時間內解決該問題。在這里工作的一種算法技術稱為有界搜索樹算法，其想法是反複選擇一些頂點和遞歸分支，每個步驟有兩個情況：將當前的頂點或所有鄰居放入頂點封面。求解最佳漸近依賴性參數的算法 。此時間限制的Klam值（可以在合理時間內可以解決的最大參數值的估計值）約為190。也就是說，除非找到其他算法改進，否則該算法僅適用封面號為190或更少。在合理的複雜性理論假設下，即指數時間假設，即使運行時間也不能提高到2 ^{O （ k ）} 是 。

但是，對於平面圖，更一般而言，對於不包括一些固定圖的圖形，可以在時間上找到大小k的頂點覆蓋物 ，即，這個問題是可以固定參數的固定參數。從某種意義上說，在指數時間假設下，該算法再次是最佳的 。

近似評估

可以通過重複將邊緣的兩個端點進入頂點蓋，然後將其從圖中刪除，從而找到因子-2近似。否則，我們找到了具有貪婪算法的最大匹配M ，並構建一個由m中邊緣的所有端點組成的頂點蓋C。在下圖中，最大匹配m用紅色標記，頂點蓋C標記為藍色。

以這種方式構造的C集C是頂點蓋：假設邊緣E不被C覆蓋；然後， m∪ { e }是一個匹配和e∉m ，這與m是最大的假設是矛盾的。此外，如果e = { u ， v } ∈M ，則任何頂點蓋（包括最佳頂點蓋）都必須包含u或v （或兩者）；否則邊緣E不會覆蓋。也就是說，最佳蓋包含M中每個邊緣的至少一個端點；總共C， C的最多是最佳頂點蓋的2倍。

這種簡單的算法是由Fanica Gavril和Mihalis Yannakakis獨立發現的。

涉及更多的技術表明，存在近似算法，其近似因子稍好一些。例如，一種近似值的近似算法已知。可以用近似因素近似該問題在 - 密集圖。

不適當的性能

沒有比上述恆定近似算法更好的恆定因子近似算法。最小頂點覆蓋問題是APX算法，也就是說，除非p = np，否則它不能任意地近似。使用來自PCP定理的技術， Dinur和Safra在2005年證明，對於任何足夠大的頂點度，除非P = NP ，否則最小頂點覆蓋率不能在1.3606倍的元素內近似。後來，該因素被提高到任何 。此外，如果唯一的遊戲猜想是正確的，則最小頂點蓋不能在任何常數因子內近似於2。

儘管找到最小尺寸的頂點覆蓋物等於找到最大尺寸的獨立集，但如上所述，這兩個問題在近似保護的方式上並不等於：獨立設置問題沒有恆定的因素近似值，除非p = np = np 。

虛擬程式碼

APPROXIMATION-VERTEX-COVER(G)
C = ∅
E'= G.E
while E' ≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v
return C

申請

頂點覆蓋優化是許多現實世界和理論問題的模型。例如，一個有興趣安裝覆蓋所有房間（節點）的所有走廊（邊緣）的商業機構可能會將目標建模為頂點覆蓋最小化問題。該問題還用於建模消除合成生物學和代謝工程應用的重複性DNA序列。