獨立集

獨立集（英語：Independent set）是圖論中的概念。一個獨立集（也稱為穩定集）是一個圖中一些兩兩不相鄰的頂點所形成的集合。換句話說，獨立集$S$由圖中若干頂點組成，且$S$中任兩個頂點之間沒有邊。等價地，圖中的每條邊至多有一個端點屬於$S$。一個獨立集的基數是它包含頂點的數目。

圖中九個藍色的頂點是延伸佩特森圖GP(12,4)中的一個最大獨立集

如果往圖$G$的獨立集$S$中添加任一個頂點都會使獨立性喪失（亦即造成某兩點間有邊），那麼稱$S$是極大獨立集。如果$S$是圖中所有獨立集之中基數最大的，那麼稱$S$是最大獨立集，且將該基數稱為$G$的獨立數，記為$\alpha (G)$。一般來講，圖$G$中可能存在多個極大獨立集；最大獨立集亦如是。最大獨立集一定是極大獨立集，但反之未必。

給定一張圖，尋找其中一個最大獨立集的問題被稱為最大獨立集問題。該問題已知是NP困難的最優化問題，且即便試圖以常數倍近似也是NP困難的。因此，計算機科學家普遍相信不存在解決該問題的高效算法，無論是精確求解還是以常數倍近似求解。

數學定義

對於圖$G=(V,E)$，如果頂點子集$S\subseteq V$滿足$\forall u,v\in S,\{u,v\}\not \in E$，則稱$S$為$G$的一個獨立集，稱$|S|$為該獨立集的基數。

對於獨立集$S$，如果$\forall v\in V\setminus S,\exists u\in S:\{u,v\}\in E$，則稱$S$是極大獨立集。直觀而言，極大意味着$S$不能單純通過加入頂點來擴充。

如果$|S|$是所有獨立集中最大的，那麼稱$S$是最大獨立集，並將$|S|$稱作$G$的獨立數（independence number），記作$\alpha (G)$。最大獨立集一定是極大獨立集；若不然，我們總能加入頂點來擴充之，從而與最大的定義矛盾。

整數規劃形式

計算獨立數$\alpha (G)$的問題可以等價表達成如下的整數規劃：

${\begin{aligned}\max \quad &\sum _{v\in V}x_{v}\\{\text{s.t.}}\quad &x_{u}+x_{v}\leq 1&\forall \{u,v\}\in E\\&x_{v}\in \{0,1\}&\forall v\in V\end{aligned}}$

其中，變量$x_{v}$取1代表把頂點$v$放入獨立集，取0則反之。第一條線性約束表達了每條邊的兩個端點不能同時放入獨立集中。

與其它圖論對象的聯繫

與頂點覆蓋的關係

圖的一個頂點覆蓋（vertex cover）是頂點集的一個子集，使得圖中每條邊都與其中某點相鄰。基數最小的頂點覆蓋稱為圖的最小頂點覆蓋。獨立集與頂點覆蓋的定義互補，因此不難看出，$S$是圖$G$的獨立集若且唯若$V\setminus S$是$G$的頂點覆蓋。於是，$\alpha (G)$就等於$G$的頂點數減去$G$的最小頂點覆蓋的基數。

與團的關係

在圖論中，團（clique）是一個與獨立集密切相關的概念。圖$G=(V,E)$的一個團指的是一個頂點子集$C\subseteq V$，使得$C$中頂點兩兩相鄰。用圖論的語言，團即一個完全的子圖。$G$的最大團的基數稱作$G$的團數（clique number），記作 $\omega (G)$。 如果說獨立集是一種水火不容的頂點集，那麼團就是一種息息相關的頂點集。不難看出，一個圖的團是其補圖的獨立集，反之亦然。這個一一對應關係使得二者性質能夠相互轉述，而與二者相關的問題往往等價。例如，圖的團數等於其補圖的獨立數，即 $\omega (G)=\alpha ({\overline {G}})$。類似地，圖$G$中團的總數等於補圖${\overline {G}}$中獨立集的總數。

對於一般的圖而言，尋找最大團是NP困難的，從而尋找最大獨立集也是NP困難的。計算機科學家普遍相信沒有算法能在確定性多項式時間解決之。但是，對於二分圖這一特殊情形，則有多種方法可以高效地求解。例如，可以求解鬆弛後的線性規劃並對結果作整數化處理，也可以使用匈牙利算法求出最小頂點覆蓋後再轉化為最大獨立集。

與點連通度的關係

圖的點連通度$\kappa (G)$定義為：最少需要刪除$\kappa (G)$個頂點方能使得圖不復連通。獨立數與點連通度有着簡單關係

$\kappa (G)\leq n-\alpha (G)$

原因是：設$S$是一個最大獨立集，把$V\setminus S$的頂點全部刪掉以後，殘餘下來的正是獨立集$S$，而它自然是不連通的。

與着色數的關係

圖的着色（proper colouring）即為每個頂點染上一種顏色，使得任意相鄰頂點顏色均不同（但不相鄰頂點顏色可以相同）。對圖$G$進行着色所需的最少顏色數被稱為$G$的着色數，記作$\chi (G)$。獨立數和着色數之間存在以下關係：

${\frac {n}{\alpha (G)}}\leq \chi (G)\leq n-\alpha (G)+1$

其中$n$是$G$中的頂點數。

證明

左側不等式：設着色$f:V\to [\chi (G)]$是一個使用顏色最少的方案，我們構造$\chi (G)$個集合$S_{1},\dots ,S_{\chi (G)}$如下。$S_{i}:=\{v\in V\mid f(v)=i\}$。也就是說，把顏色相同的節點放入同一個集合。這些集合構成了頂點集的一個劃分，所以${\textstyle n=\sum _{i=1}^{\chi (G)}|S_{i}|}$。注意到每個集合都各是一個獨立集（因為相同顏色的頂點之間不允許有邊），所以$|S_{i}|\leq \alpha (G)$對它們均成立。代入先前等式便有${\textstyle n\leq \chi (G)\cdot \alpha (G)}$ 右側不等式：設$S$是一個最大獨立集，我們據此構造一種着色$f$。首先，$f$給$S$中所有頂點均染上顏色1（這必定不會造成衝突）。其次，$f$給其餘頂點分配互異且非1的顏色。容易看出$f$僅僅使用了$1+|V\setminus S|=1+n-\alpha (G)$種顏色，因此着色數必定不少於該數。

計算複雜性

求最大獨立集是計算機科學中的重要問題，因為許多現實場景可以抽象成該問題。例如，人們希望組織一場會議，候選的某些演講者之間或有嫌隙，不願同時出席。可以將這種候選人之間敵意關係抽象成一張圖，兩個候選人間有邊若且唯若二者不和。那麼，最終的演講者名單就應當是這張圖的一個獨立集。會議組織者希望邀請儘可能多的演講者以充實內容，也就相當於尋找圖中的最大獨立集。

然而，計算複雜性理論在以下兩方面的進展暗示該問題難以求解。

判定版本的NP完備性

考慮最大獨立集問題的判定版本：給定一張圖和一個目標$I$，圖中是否存在一個獨立集的基數不小於$I$？在先前的例子中，相當於：會議組織者預先設定了一個目標邀請人數，問這個目標能否實現？其實，判定版本並不比原始版本簡單。假設我們能夠高效解決判定版本，那麼也可以藉助自歸約性質（self-reducibility），相對高效地解決原始版本。

最大獨立集問題的判定版本是NP完備的，這意味着，除非${\textsf {P}}={\textsf {NP}}$（而人們普遍相信這是不可能的），否則不存在確定性多項式時間算法解決之。其完備性的證明可以參見。

優化版本的不可近似性

考慮最大獨立集問題的優化版本：給定一張圖$G$，計算$\alpha (G)$。該問題是MAXSNP完備的，這意味着，除非${\textsf {P}}={\textsf {NP}}$，否則不存在確定性多項式時間算法能以任意精度近似之（PTAS）。

還可以證明：假若存在某個高效算法能以某常數$c>0$為近似比計算該問題，那麼就能據此構造出一個以任意精度近似計算該問題的高效算法（PTAS）。結合前面的結論可知：除非${\textsf {P}}={\textsf {NP}}$，否則不存在高效算法能以常數倍近似計算該問題。