獨立集（independent set）

獨立集是團的相反。它不是一群人人相連的群體，而是一群「沒有任何兩個成員相連」的群體：一組互不相識的人，任何一對之間都沒有邊。想像挑選必須毫無利益衝突的委員：任何兩個共用一條邊的人不能同時任職。獨立集問題問：你能否找到這樣一個大小至少為給定值 k 的無衝突群體？

形式上，無向圖 G 中的獨立集是一組頂點，其中任何兩個之間都沒有邊。判定問題 INDEPENDENT-SET 接收 G 與一個數 k，問是否存在大小為 k 的獨立集。它屬於 NP：候選集合就是證書，驗證器在多項式時間內檢查它內部沒有任何一對是邊。三個手足問題形成緊密的一群：G 中的獨立集恰恰是補圖 G-bar 中的團，而獨立集（在頂點集內）的補集是一個頂點覆蓋。所以「大小為 k 的獨立集」、「G-bar 中大小為 k 的團」、「大小為 n - k 的頂點覆蓋」說的是同一件事。

由於這些等價，INDEPENDENT-SET 是 NP 完全：難度由 CLIQUE 流入（經由取補圖）或直接由 3-SAT 而來，而屬於 NP 是顯然的。三人組 CLIQUE／INDEPENDENT-SET／VERTEX-COVER 通常被一起教，正因為一個快速歸約就把三者連起。獨立集也模擬真實的「無衝突裝填」任務，像排不重疊的活動、或選不互相干擾的無線頻道，這就是為何它在應用中不斷出現，儘管它的一般版難以求解。