獨立集

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

圖中九個藍色的頂點是延伸佩特森圖（英語：Generalized Petersen graph）GP(12,4)中的一個最大獨立集

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

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

數學定義

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

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

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

整數規劃形式

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

${\displaystyle {\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}}}$

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

與其它圖論對象的聯繫

與頂點覆蓋的關係

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

與團的關係

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

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

與點連通度的關係

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

${\displaystyle \kappa (G)\leq n-\alpha (G)}$

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

與着色數的關係

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

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

其中${\displaystyle n}$是${\displaystyle G}$中的頂點數。

證明

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

計算複雜性

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

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

判定版本的NP完備性

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

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

優化版本的不可近似性

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

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

參考資料

1. Chris Godsil and Gordon Royle. Algebraic Graph Theory. New York: Springer. 2001: p. 3. ISBN 0-387-95220-9. 引文格式1維護：冗餘文本 (link)
2. Sipser, Michael. Introduction to the Theory of Computation, Third Edition. Cengage Learning. 2013: pp. 311–313. ISBN 978-1-133-18779-0. 引文格式1維護：冗餘文本 (link)
3. Papadimitriou, Christos H. Computationaly Complexity. Addison Wesley Longman. 1994: pp. 309–322. ISBN 0-201-53082-1. 引文格式1維護：冗餘文本 (link)