NP-Complete圖優化：最小節點選擇？

Question

假設您有一張圖表G = (V, E)，表示一層購物中心的平面圖。各個商店由頂點表示，並且頂點之間的邊代表一些商店的任意定義彼此接近。

最近，一直在商店行竊的發生在這家商場的量的增加，所以管理層決定讓這個每家商店之一：

• 已進駐它

一名保安

• 或者是接近了駐紮在它

雖然僱用儘可能少的保安儘可能一名保安的商店。

你會如何證明這個優化問題是NP完全的？我覺得這是從獨立設置問題簡單減少，但我想確保。

Answer 1

這正是minimum vertex cover problem這是已知是NP完全。在看到該計算的最小頂點蓋的尺寸等同於計算最大獨立集的大小的關鍵見解是：

A set of vertices is a vertex cover, if and only if its complement is an independent set.

特別地，這意味着，頂點的總數是等於最小頂點覆蓋的大小加上最大獨立集合的大小。這很好地說明了如何計算一個數字減少到計算另一個數字。