最小頂點覆寫(Minimum Vertex Cover)與最大獨立集(Maximum Independent Set)

問題描述：就是在圖中找最小的點集，使得覆寫所有邊。

和獨立集等價：獨立集問題：在圖中找最大的點集，使得點集内的所有點互不相連。

引理：頂點覆寫集和獨立集互補。

上面這個引理使得這兩個問題可以互相規約，進而這兩個問題等價。

等價問題：給定圖G和數k, 問G包含大小至少為k的獨立集嗎？

為什麼等價：如果我們能在多項式時間内給出這個問題的答案，那麼我們可以通過二分查找得到最大獨立集的size為K。一個點如果是最大獨立集中的點，等價于除去這個點後得到的圖G'含有一個K-1大小的獨立集。那麼我們每次選取一個頂點v，然後再問一下G'是否有K-1的獨立集，如果回答為yes，那麼我們把v加入我們的答案中，如果回答為no, 我們把v的鄰居加入答案中（因為如果v不在答案中，v的鄰居也不在答案中，那麼v和鄰居之間的邊将不會被覆寫）。是以，如果上述提問的解法是多項式的，那麼最大獨立集問題也是多項式的。