我們說圖 $G$ 上的一個點的子集合 $S\subseteq V$ 是獨立集（Independent Set），若且唯若 $G[S]$ 沒有任何邊。
透過直接的觀察可以得知，$S$ 在 $G$ 上是一個獨立集，等價於 $\overline{G}[S]$ 是一個完全子圖，其中 $\overline{G}$ 是 $G$ 的補圖（Complement Graph）。從這個觀察也可以知道，如果我們要列舉出所有極大獨立集（Maximal Independent Set, MIS），那麼所有適用於前一節找 Maximal Clique 的演算法也通通都適用於此。
相對應地，我們令 $\alpha(G)$ 表示為圖 $G$ 上最大獨立集的大小。關於這個獨立集的大小，
§8.1 關於 $\alpha(G)$ 的估計
這個定理有個利用隨機演算法輕鬆證明的結論，它在平行與分散式計算上面找極大獨立集有非常顯著的應用，大家可以參考 CMU 的 Luby演算法講義。
§8.2 找出最大獨立集
顯然枚舉所有點的子集合逐一檢查可以做到 $O(n^2 2^n)$、利用前一節列舉極大完全子 圖所需要的時間為 $O(3^{n/3})\approx O(1.4422^n)$。在此我們提供一個坊間謠傳的簡單暴搜方法：
如果一個圖 $G$ 的最大度數 $\Delta(G) \le 2$，那麼顯然這個圖是由很多路徑和圈構成的。此時我們可以在多項式時間內找出最大獨立集。因此我們不妨假設所有遞迴中遇到的子問題，其最大度數都是 $\ge 3$。
DFS 的方法如下：我們每次選取當前圖上度數最大的點 $v$，由於前面的假設我們知道 $\deg(v) \ge 3$。接下來，透過簡單的觀察可以知道：一個最大的獨立集要嘛包含 $v$ 但是不包含任何 $v$ 的鄰居 $\Gamma(v)$（一個遞迴呼叫 $G-\set{v}-\Gamma(v)$）、要嘛就不包含 $v$（另一個遞迴呼叫 $G-\set{v}$）。
因此可以直接將時間複雜度的上界寫下來：
$$ T(n) \le T(n-1) + T(n-4) + \text{poly}(n) $$
有一點點像 Master Theorem 的感覺，這類型的遞迴關係是有一些簡單的方法可以輕鬆推導出時間複雜度的。我們不妨假設有個實數常數 $c$ 使得 $T(n) = c^n$。只要 $c$ 滿足 $c^3 + 1 < c^4$ 就可以讓上面的遞迴式成立了。
透過解方程式，我們可以知道選取 $c\approx 1.3803$ 能夠滿足條件。因此我們證得上述演算法時間複雜度為 $O(1.3803^n)$。把這個方法延伸，考慮更多的 case （度數 3, 4, 5 的點等等），就會得到 Tarjan [1977] 這篇論文的 $O(1.2599^n)$ 的上界。考慮更多更多更多的 case （度數 1~9 的點等等），再加上一些記憶化搜索的技巧就會得到 Robson [2001] 這篇論文的 $O(1.1888^n)$ 時間複雜度了。下面介紹兩個被用在 Robson 演算法裡面的加速技巧，這些技巧被廣泛應用在其他題目中，以後我們有機會碰到也會再次提及。
加速技巧：Indirection
一個有 $n$ 個點的圖，其點數不超過 $\delta n$ 的誘導子圖，數量不超過 ${n\choose {\delta n}}$ 個。使用 Strling's Formula 這個值算起來大概是 $$ \left(\frac{1}{\delta^\delta (1-\delta)^{1-\delta}}\right)^n $$。
假設最原始的圖有 $N$ 個點，把這個方法代入原本的遞迴式以後，所有的遞迴動作會在 $n < \delta N$ 的時候中止。因此撇開動態規劃的時間不算，等效的遞迴時間複雜度是 $T(N-\delta N) = c^{(1-\delta)N}$。如果我們套用上面簡單演算法得到的 $c=1.3803$，我們可以隨意選取 $\delta=0.09$，這樣時間複雜度可以變成 $O(\max\set{c^{0.91}, 1.3533}^N)$，得到效率的提升。
把加速技巧加速：Memoization
證明
固定一個圖 $G$ 的連通誘導子圖，我們可以從任意一個點出發，畫出一棵 BFS 樹。顯然不同的誘導子圖（點集合不同）會造出不同的 BFS 樹。所以誘導子圖 $\leftrightarrow$ BFS 樹是一個一對多（1-to-many）的關係。只要我們給出所有這樣的 BFS 樹的數量上界，就能夠說明誘導子圖數量的上界。
根據題目條件，每個點度數不超過 8。因此除了根節點以外，其他的點的子節點數量都不超過 7。根據 Fuss-Catalan 公式，這樣子的樹會 有 $\text{poly}(n){7n\choose n}$ 左右。（註：可參考 OEIS http://oeis.org/A002296）
上面這個定理要怎麼用來加速呢？如果我們只紀錄「點的總數不超過 $\delta n$、並且該連通誘導子圖上所有點度數都不超過 8」的圖，那麼這樣的誘導子圖的總數不會超過 $\text{poly}(n){{7\delta n} \choose {\delta n}}\approx \text{poly}(n)(7^76^{-6})^{\delta n}$。當 $\delta \le 1/7$ 的時候，用這個方法會比第一種技巧需要的狀態總數來得少。
存在度數超過 8 的點的時候怎麼辦？這時候只要用老樣子遞迴就行啦～$$ T(n) = T(n-1) + T(n-9) + \text{poly}(n)$$ 解出來大概是 $(1.2132)^n$，只要我們選擇的 $\delta$ 不要太小，就可以讓 $(7^76^{-6})^{\delta n}$ 這項大過這個時間複雜度。
§8.3 習題
- 證明題 利用「度數為 2 的點可以忽略不計」這個觀察，證明上述演算法的另一種分析方式：
$$ T(n) \le \begin{cases} T(n-1)+T(n-5) + \text{poly}(n)\ 2T(n-4)+ \text{poly}(n) \end{cases} $$ 而得出 $T(n) = O(1.3247^n)$ 的結論。 2. 思考題 解釋為什麼上述 DFS 方法找出最大獨立集的方法，沒辦法（在同樣時間複雜度情形下）「列舉」所有的極大獨立集。