頂點覆蓋（vertex cover）

想像一張城市地圖，邊是街道、頂點是路口，你想在某些路口放守衛，使「每條」街道的兩端至少有一端有守衛。能看守所有街道的最少守衛數，就是最小頂點覆蓋。頂點覆蓋問題問：這份工作能否用至多 k 個守衛完成？

形式上，無向圖 G 的頂點覆蓋是一組頂點，使得每條邊至少有一個端點落在這組裡。判定問題 VERTEX-COVER 接收 G 與一個數 k，問是否存在大小至多 k 的頂點覆蓋。它屬於 NP：一組候選的 k 個頂點就是證書，驗證器在多項式時間內掃過每條邊，確認每條都被覆蓋。最佳化版——找最小覆蓋——是它 NP 困難的表親。

VERTEX-COVER 是 NP 完全，而最乾淨的證明搭在一個漂亮的恆等式上：集合 S 是 G 的頂點覆蓋，當且僅當其餘頂點（所有「不」在 S 裡的）構成一個獨立集，它們之間沒有邊。所以 G 有大小為 k 的頂點覆蓋，恰恰當 G 有大小為 n - k 的獨立集時（n 為頂點數）。這就立刻給出與獨立集互相的歸約，並透過它從 3-SAT 而來，於是頂點覆蓋加入了標準工具箱。重要的是，頂點覆蓋也是「應對 NP 困難」的明星範例：它有一個簡單的二倍近似（反覆挑一條未覆蓋邊的兩個端點）並對 k 是固定參數可解，所以這份難度遠非死路。