支配集

在圖論中，一個圖 G 的支配集是其頂點的一個子集 D，使得 G 的任何頂點要嘛屬於 D，要嘛與 D 中的某個頂點相鄰。支配數 γ(G) 是 G 的最小支配集中的頂點數。

支配集問題旨在測試對於給定的圖 G 和輸入 K，是否有 γ(G) ≤ K；這是計算複雜度理論中一個經典的 NP 完全決策問題。因此，一般認為可能不存在能對所有圖 G 計算出 γ(G) 的高效演算法。然而，目前已有效率的近似演算法，以及針對特定圖類的高效精確演算法。

支配集在數個領域中具有實用價值。在無線網路中，支配集被用來尋找行動隨意網路中的高效路由。它們也已被應用於文件摘要，以及設計電網的安全系統。

形式化定義

給定一個無向圖 <math>G=(V,E)</math>，一個頂點子集 <math>D\subseteq V</math> 稱為支配集，如果對於每個頂點 <math>u\in V\setminus D</math>，都存在一個頂點 <math>v\in D</math> 使得 <math>\{u,v\} \in E</math>。

每個圖至少有一個支配集：如果 <math>D=V=</math> 所有頂點的集合，那麼根據定義 D 就是一個支配集，因為不存在頂點 <math>u\in V\setminus D</math>。一個更有趣的挑戰是找到小的支配集。圖 G 的支配數定義為： <math>\gamma(G) := \min \{|D| : D \text{ 是 } G \text{ 的一個支配集} \}</math>。

變體

連通支配集是一種本身也連通的支配集。若 S 是一個連通支配集，則可以建構 G 的一個生成樹，其中 S 構成該樹的非葉節點集合；反之，若 T 是頂點數多於兩個的圖中的任意生成樹，則 T 的非葉節點會形成一個連通支配集。因此，尋找最小連通支配集等同於尋找具有最大可能葉子數的生成樹。

全支配集（或稱強支配集）是一個頂點集合，使得圖中的所有頂點，包括支配集本身的頂點，都在該支配集中有鄰點。也就是說：對於每個頂點 <math>u\in V</math>，都存在一個頂點 <math>v\in D</math> 使得 <math>\{u,v\} \in E</math>。上方的圖 (c) 顯示了一個既是連通支配集也是全支配集的支配集；圖 (a) 和 (b) 的例子則兩者皆非。與簡單支配集不同，全支配集可能不存在。例如，一個擁有一或多個頂點但沒有邊的圖就沒有全支配集。G 的強支配數定義為： <math>\gamma^{strong}(G) := \min \{|D| : D \text{ 是 } G \text{ 的一個強支配集} \}</math>；顯然，<math>\gamma^{strong}(G) \geq \gamma(G)</math>。

支配邊集是一個邊（頂點對）的集合，其聯集是一個支配集；這樣的集合可能不存在（例如，一個擁有一或多個頂點但沒有邊的圖就沒有）。如果存在，其所有邊的聯集就是一個強支配集。因此，一個邊支配集的最小尺寸至少為 <math>\gamma^{strong}(G) /2</math>。

相對地，一個邊支配集是一個邊的集合 D，使得 D 以外的每條邊都與 D 中的至少一條邊相鄰；這樣的集合總是存在（例如，所有邊的集合就是一個邊支配集）。

k-支配集 是一個頂點集合，使得集合外的每個頂點在集合內至少有 k 個鄰點（標準的支配集是 1-支配集）。類似地，'k-元組支配集' 是一個頂點集合，使得圖中的每個頂點在集合內至少有 k 個鄰點（全支配集是 1-元組支配集）。一個近似的最小 k-元組支配集可在多項式時間內找到。每個圖都容許一個 k-支配集（例如，所有頂點的集合）；但只有最小度為 <math>k-1</math> 的圖才容許 k-元組支配集。然而，即使圖容許 k-元組支配集，其最小 k-元組支配集的大小也可能幾乎是同一個圖的最小 k-支配集的 k 倍；一個近似的最小 k-支配集亦可在多項式時間內找到。

星支配集是 V 的一個子集 D，使得對於 V 中的每個頂點 v，v 的星（與 v 相鄰的邊的集合）與 D 中某個頂點的星相交。顯然，如果 G 有孤立頂點，則它沒有星支配集（因為孤立頂點的星是空的）。如果 G 沒有孤立頂點，則每個支配集都是星支配集，反之亦然。當考慮其分數變體時，星支配與普通支配之間的區別更為顯著。

支配劃分是將頂點劃分為互不相交的支配集。支配劃分數是一個支配劃分的最大規模。

永恆支配集是支配問題的一個動態版本，其中支配集 D 中的一個頂點 v 被選中，並被一個鄰點 u（u 不在 D 中）取代，使得修改後的 D 仍然是一個支配集，且此過程可以對任何無限的頂點 v 選擇序列重複進行。

支配集與獨立集

支配集與獨立集密切相關：一個獨立集同時也是一個支配集，若且唯若它是一個極大獨立集。因此，圖中的任何極大獨立集必然也是一個極小支配集。

以獨立集進行支配

支配集可能是也可能不是獨立集。例如，上方的圖 (a) 和 (b) 顯示了獨立支配集，而圖 (c) 則說明了一個非獨立集的支配集。

圖 <math>G</math> 的獨立支配數 <math>i(G)</math> 是本身為獨立集的最小支配集的大小。等價地，它是最小極大獨立集的大小。<math>i(G)</math> 中的最小值是在較少的元素上取得的（只考慮獨立集），因此對於所有圖 <math>G</math>，<math>i(G) \geq \gamma(G)</math>。

這個不等式可以是嚴格的—存在圖 <math>G</math> 使得 <math>i(G) > \gamma(G)</math>。例如，令 <math>G</math> 為雙星圖，其頂點為 <math>\{c_1, c_2, p_{1,1}, \dots, p_{1,n}, p_{2,1}, \dots, p_{2,n}\}</math>，其中 <math>n\geq 2</math>。<math>G</math> 的邊定義如下：每個 <math>p_{1,j}</math> 與 <math>c_1</math> 相鄰，<math>c_1</math> 與 <math>c_2</math> 相鄰，且 <math>c_2</math> 與每個 <math>p_{2,j}</math> 相鄰。那麼 <math>\gamma(G)=2</math>，因為 <math>\{c_1,c_2\}</math> 是一個最小支配集。如果 <math>n\geq 2</math>，則 <math>i(G)=n+1</math>，因為 <math>\{c_2, p_{1,1}, \dots, p_{1,n}\}</math> 是一個同時也是獨立集的最小支配集（它是一個最小極大獨立集）。

有些圖族中 <math>i(G)=\gamma(G)</math>，也就是說，每個最小極大獨立集都是一個最小支配集。例如，如果 <math>G</math> 是一個無爪圖，則 <math>i(G)=\gamma(G)</math>。

如果圖 <math>G</math> 的每個導出子圖 <math>H</math> 中都有 <math>i(H)=\gamma(H)</math>，則稱 <math>G</math> 為支配完美圖。由於無爪圖的導出子圖也是無爪的，因此每個無爪圖也都是支配完美圖。

對於任何圖 <math>G</math>，其線圖 <math>L(G)</math> 是無爪的，因此 <math>L(G)</math> 中的最小極大獨立集也是 <math>L(G)</math> 中的最小支配集。<math>L(G)</math> 中的一個獨立集對應於 <math>G</math> 中的一個匹配，而 <math>L(G)</math> 中的一個支配集對應於 <math>G</math> 中的一個邊支配集。因此，一個最小極大匹配的大小與一個最小邊支配集的大小相同。

對獨立集的支配

圖 <math>G</math> 的獨立集支配數 <math>i\gamma(G)</math> 是指，對於 <math>G</math> 的所有獨立集 <math>I</math>，支配 <math>I</math> 的最小集合大小的最大值。支配頂點的子集可能比支配所有頂點需要更少的頂點，因此對於所有圖 <math>G</math>，<math>i\gamma(G) \leq \gamma(G)</math>。

這個不等式可以是嚴格的—存在圖 <math>G</math> 使得 <math>i\gamma(G) < \gamma(G)</math>。例如，對於某個整數 <math>n\geq 2</math>，令 <math>G</math> 是一個圖，其頂點是一個 <math>n \times n</math> 棋盤的行和列，且兩個這樣的頂點相連若且唯若它們相交。唯一的獨立集是僅由行構成的集合或僅由列構成的集合，而它們中的每一個都可以被單一頂點（一個列或一個行）支配，因此 <math>i\gamma(G)=1</math>。然而，要支配所有頂點，我們至少需要一行和一列，所以 <math>\gamma(G)=2</math>。此外，<math>\gamma(G)</math> 和 <math>i\gamma(G)</math> 之間的比率可以任意大。例如，如果 <math>G</math> 的頂點是一個 <math>n \times n</math> 棋盤上所有方格的子集，則仍然有 <math>i\gamma(G)=1</math>，但 <math>\gamma(G)=n^2</math>。

圖 <math>G</math> 的雙獨立支配數 <math>i\gamma i(G)</math> 是指，對於 <math>G</math> 的所有獨立集 <math>I</math>，支配 <math>I</math> 的最小獨立集大小的最大值。對於任何圖 <math>G</math>，以下關係成立： <math display="block">\begin{align} i(G)&\geq \gamma (G) \geq i\gamma(G) \\ i(G)&\geq i\gamma i(G) \geq i\gamma(G) \end{align}</math>

歷史

支配問題自 1950 年代起就有人研究，但對支配問題的研究速度在 1970 年代中期顯著加快。1972 年，理查·卡普證明了集合覆蓋問題為 NP 完全問題。這對支配集問題產生了直接影響，因為在這兩個問題之間存在直接的頂點到集合以及邊到非不交集交集的對射。這也證明了支配集問題是 NP 完全的。

演算法與計算複雜度

集合覆蓋問題是一個著名的 NP 困難問題—集合覆蓋的決策版本是卡普的 21 個 NP 完全問題之一。在最小支配集問題和集合覆蓋問題之間存在一對多項式時間的 L-歸約。這些歸約（見下文）表明，一個用於最小支配集問題的高效演算法將能提供一個用於集合覆蓋問題的高效演算法，反之亦然。此外，這些歸約保留了近似比：對於任何 α，一個用於最小支配集的多項式時間 <math>\alpha</math>-近似演算法將能提供一個用於集合覆蓋問題的多項式時間 <math>\alpha</math>-近似演算法，反之亦然。事實上，這兩個問題都是 Log-APX-完全的。

集合覆蓋的可近似性也已得到充分理解：使用簡單的貪婪演算法可以找到一個對數級的近似因子，而找到一個次對數級的近似因子是 NP 困難的。更具體地說，貪婪演算法提供了最小支配集的一個 <math>(1+\ln |V|)</math> 因子近似，並且除非 P = NP，否則對於某個 <math>c>0</math>，沒有任何多項式時間演算法能達到優於 <math>c \ln |V|</math> 的近似因子。

L-歸約

以下兩個歸約表明，最小支配集問題和集合覆蓋問題在 L-歸約下是等價的：給定其中一個問題的一個實例，我們可以建構另一個問題的一個等價實例。

從支配集到集合覆蓋

給定一個有 <math>n</math> 個頂點的圖 <math>G=(V,E)</math>，建構一個集合覆蓋實例 <math>(U, \mathcal{F})</math> 如下：全集 <math>U</math> 為 <math>V</math>，子集族為 <math>\mathcal{F}=\{S_v\}_{v\in V}</math>，其中 <math>S_v</math> 由頂點 <math>v</math> 及 <math>G</math> 中所有與 <math>v</math> 相鄰的頂點組成。

現在，如果 <math>D</math> 是 <math>G</math> 的一個支配集，那麼 <math>C=\{S_v:v\in D\}</math> 是集合覆蓋問題的一個可行解，且 <math>|C|=|D|</math>。反之，如果 <math>C=\{S_v:v\in D\}</math> 是集合覆蓋問題的一個可行解，那麼 <math>D</math> 就是 <math>G</math> 的一個支配集，且 <math>|D|=|C|</math>。

因此，<math>G</math> 的最小支配集大小等於 <math>(U,\mathcal{F})</math> 的最小集合覆蓋大小。此外，有一個簡單的演算法可以將一個支配集對映到一個大小相同的集合覆蓋，反之亦然。特別是，一個高效的集合覆蓋 <math>\alpha</math>-近似演算法可提供一個高效的最小支配集 <math>\alpha</math>-近似演算法。

例如，給定右側所示的圖 <math>G</math>，我們建構一個集合覆蓋實例，其全集為 <math>U=\{1,2,3,4,5,6\}</math>，子集為 <math>S_1=\{1,2,5\}, S_2=\{1,2,3,6\}, \dots</math> 和 <math>S_6=\{2,5,6\}</math>。在此例中，<math>D=\{3,5\}</math> 是 <math>G</math> 的一個支配集——這對應於集合覆蓋 <math>C=\{S_3, S_5\}</math>。例如，頂點 <math>4</math> 被頂點 <math>3</math> 支配，而元素 <math>4</math> 包含在集合 <math>S_3</math> 中。

從集合覆蓋到支配集

設 <math>(U, \mathcal{F})</math> 是一個集合覆蓋問題的實例，其全集為 <math>U</math>，子集族為 <math>\mathcal{F}=\{S_i\}_{i\in I}</math>；我們假設 <math>U</math> 和索引集 <math>I</math> 是不相交的。建構一個圖 <math>G=(V,E)</math> 如下：頂點集為 <math>V = U \cup I</math>，每對 <math>i,j\in I</math> 之間有一條邊 <math>\{i,j\}</math>，並且對於每個 <math>i\in I</math> 和 <math>u \in S_i</math> 也有一條邊 <math>\{i,u\}</math>。也就是說，<math>G</math> 是一個分割圖：<math>I</math> 是一個完全圖，而 <math>U</math> 是一個獨立集。

現在，如果 <math>C=\{S_i:i\in I'\}</math> 對於某個子集 <math>I' \subseteq I</math> 是集合覆蓋問題的一個可行解，那麼 <math>I'</math> 就是 <math>G</math> 的一個支配集，且 <math>|I'|=|C|</math>：首先，對於每個 <math>u\in U</math>，存在一個 <math>i\in I'</math> 使得 <math>u \in S_i</math>，根據建構，<math>u</math> 和 <math>i</math> 在 <math>G</math> 中是相鄰的；因此 <math>u</math> 被 <math>I'</math> 支配。其次，由於 <math>I</math> 必須非空，每個 <math>i\in I \setminus I'</math> 都與 <math>I'</math> 中的一個頂點相鄰。

反之，設 <math>D</math> 是 <math>G</math> 的一個支配集。那麼可以建構另一個支配集 <math>D'</math>，使得 <math>|D'|\leq |D|</math> 且 <math>D'\subseteq I</math>：只需將每個 <math>u\in D\cap U</math> 替換為 <math>u</math> 在 <math>I</math> 中的一個鄰點 <math>i_u</math>。那麼 <math>\{S_i : i\in D'\}</math> 是集合覆蓋問題的一個可行解，其大小為 <math>|D'|</math>。

右圖顯示了 <math>U=\{1,2,3,4\}</math>、<math>I=\{a,b,c\}</text>、<math>S_a=\{1,4\}, S_b=\{1,2,3\}</math> 和 <math>S_c=\{2,3,4\}</math> 的建構過程。

在此例中，<math>C=\{S_a, S_b\}</math> 是一個集合覆蓋；這對應於支配集 <math>D=\{a,b\}</math>。

<math>D=\{1,c\}</math> 是圖 <math>G</math> 的另一個支配集。給定 <math>D</math>，我們可以建構一個不大於 <math>D</math> 且為 <math>I</math> 的子集的支配集 <math>D'=\{a,c\}</math>。支配集 <math>D'</math> 對應於集合覆蓋 <math>C'=\{S_a, S_c\}</math>。

特殊情況

如果圖的最大度為 Δ，則貪婪近似演算法可找到最小支配集的一個 <math>H(\Delta+1)</math>-近似。此外，設 <math>d_g</math> 是使用貪婪近似得到的支配集的大小，則以下關係成立：<math> d_g \le N+1 - \sqrt{2M+1}</math>，其中 <math>N</math> 是給定無向圖中的節點數，<math>M</math> 是邊數。對於固定的 Δ，這使其符合 APX 成員的資格；事實上，它是 APX-完全的。

對於單位圓盤圖和平面圖等特殊情況，此問題容許多項式時間近似方案（PTAS）。在串並聯圖中，最小支配集可以在線性時間內找到。

精確演算法

一個 <math>n</math>-頂點圖的最小支配集可以透過檢查所有頂點子集，在 <math>O(2^n n)</math> 時間內找到。Fomin、Grandoni 與 Kratsch (2009) 展示了如何在 <math>O(1.5137^n)</math> 時間和指數空間內，以及在 <math>O(1.7159^n)</math> 時間和多項式空間內找到最小支配集。一個更快的演算法由 Rooij 與 Bodlaender (2011) 提出，使用 <math>O(1.4889^n)</math> 時間，他們還表明最小支配集的數量也可以在此時間內計算出來。極小支配集的數量最多為 <math>1.7159^n</math>，並且所有這些集合都可以在 <math>O(1.7159^n)</math> 時間內列出。

參數化複雜度

尋找大小為 <math>k</math> 的支配集在參數化複雜度理論中扮演著核心角色。它是 W[2] 類別中最著名的完全問題，並在許多歸約中用以證明其他問題的難解性。特別是，此問題不是固定參數可解的，意即除非 W-層級結構崩塌至 FPT=W[2]，否則不存在任何執行時間為 <math>f(k) \cdot n^{O(1)}</math>（對於任意函數 <math>f</math>）的演算法。

另一方面，如果輸入圖是平面圖，此問題仍然是 NP 困難的，但已知存在固定參數演算法。事實上，此問題有一個大小與 <math>k</math> 成線性關係的核，並且可以透過將動態規劃應用於核的分支分解，獲得在 <math>\sqrt k</math> 上為指數級且在 <math>n</math> 上為三次方的執行時間。更一般地，當以支配集大小 <math>k</math> 和最小禁止完全二分圖子圖的大小兩者作為參數時，支配集問題及其許多變體是固定參數可解的；也就是說，該問題在無雙團圖上是 FPT 的，這是一個非常廣泛的稀疏圖類別，其中包括平面圖。

支配集的補集，即非阻礙集，可以透過一個在任何圖上運行的固定參數演算法找到。

參見

• Vizing猜想 - 關聯了圖的笛卡兒積的支配數與其因子的支配數。
• 集合覆蓋問題
• 束縛數
• 非阻礙集 - 支配集的補集。

延伸閱讀

• .
• .
• .
• .
• .

Category:圖論物件 Category:NP完全問題 Category:圖論中的計算問題