獨立集

<image>

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

如果往圖$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} <pre> \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 </pre> \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\}$。也就是說，把顏色相同的節點放入同一個集合。這些集合構成了頂點集的一個劃分，所以$n = \sum_{i=1}^{\chi(G)} |S_i|$。注意到每個集合都各是一個獨立集（因為相同顏色的頂點之間不允許有邊），所以$|S_i| \leq \alpha(G)$對它們均成立。代入先前等式便有$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}$，否則不存在高效演算法能以常數倍近似計算該問題。