domination

domination是一個泛稱，專指「支配鄰近元件」這一類的圖論主題，例如packing與covering。

「填裝packing」是使用一種元件，填滿圖上全部的點、或者邊。元件用量越多越好。

例如選一些點，但是互不相鄰，稱作independent set。

「覆蓋covering」是使用一種元件，蓋住圖上全部的點、或者邊。元件用量越少越好。

例如拿一些點，蓋住所有鄰點，稱作dominating set；例如拿一些點，蓋住所有邊，叫做vertex cover；例如拿一些邊，蓋住所有點，叫做edge cover。

independent set

無向圖上，選定數點，互不相鄰，稱作「獨立集」。

各點之間不相鄰，換到補圖上面就是，各點之間都有邊。原圖的clique，就是補圖的independent set；原圖的independent set，就是補圖的clique。

maximum independent set [NP-complete]
無向圖上，點數最多的maximum independent set。

maximum independent set in tree [P]
當給定的圖是樹，得利用greedy method求解。

maximum independent set in bipartite graph [P]
當給定的圖是二分圖，得利用maximum cardinality bipartite matching求解。

UVa 193 11065 11069 1220

independent edge set（matching）

無向圖上，選定數邊，互不相鄰，稱作「邊獨立集」。正是先前介紹的「匹配」。

maximum independent set

由於是NP-complete問題，目前沒有多項式時間演算法。

一般都是採用backtracking計算maximum independent set。亦得改為計算maximum clique，請見本站文件「maximal clique enumeration: Bron–Kerbosch algorithm」。

maximum independent set in tree

以邊邊角角的點作為最大獨立集，似乎還不錯。

在樹上，邊邊角角的點就是樹葉。divide-and-conquer method，觀察樹葉及其鄰點，將問題分割成四種情況：

一、樹葉與父親都是最大獨立集：不成立。
二、樹葉與父親都不是最大獨立集：那不如採用三或四，獨立集更大。
三、樹葉是，父親不是：可以一試。
四、樹葉不是，父親是：可以一試。

以樹葉作為最大獨立集，不但填裝比較多點，而且剩餘的圖比較大張、得以填裝更多點！

greedy method。由樹葉往樹根方向選出獨立集，儘量選擇樹葉，最後就得到最大獨立集。不過這種方式無法得到字典順序最小的最大獨立集。

時間複雜度等於一次graph traversal的時間。

一、建立DFS tree，找出preorder。
二、以preorder的逆序，選出independent set。

一、建立BFS tree，找出levelorder。
二、以levelorder的逆序，選出independent set。

const int V = 9; int adj[9][9]; // adjacency matrix bool visit[9]; // DFS visit record int parent[9]; // DFS tree int order[9]; // preorder int t = 0; bool independent[9]; // maximum Independent set void DFS(int i) { order[t++] = i; visit[i] = true; for (int j=0; j<V; ++j) if (adj[i][j] && !visit[j]) { DFS(j); parent[j] = i; } } void maximum_independent_set() { memset(visit, false, sizeof(visit)); memset(parent, -1, sizeof(parent)); t = 0; DFS(0); memset(independent, true, sizeof(independent)); for (int k=V-1; k>=0; --k) { int i = order[k]; // get a leaf if (!independent[i]) continue; // removed // independent[i] = false; // remove child if (parent[i] != -1) // remove parent independent[parent[i]] = false; } }

maximum independent set in bipartite graph

二分圖當中，「最大點獨立集」與「最大邊獨立集」關係密切！

首先找到最大二分匹配，可以分類成三種情況：

甲、X側未匹配點的交錯樹們。
乙、Y側未匹配點的交錯樹們。
丙、皆是已匹配點的交錯環們（包含單獨的匹配邊）。

這三個情況互不干涉，是數塊連通分量。用graph traversal建立甲、乙的交錯樹們，剩下部分就是丙。

在二分圖上，邊邊角角的點就是交錯樹的樹葉，而交錯樹的樹葉總是位於偶數距離。要找最大點獨立集，甲、乙是取盡偶數距離的點，丙是取盡偶數距離的點、或者是取盡奇數距離的點，每塊連通分量可以各自為政。最大獨立集的大小，就是匹配邊的數量加上未匹配點的數量。小心處理，還可以得到字典順序最小的最大獨立集。

已經有最大二分匹配時，求最大點獨立集，時間複雜度等於一次graph traversal的時間。

const int X = 9, Y = 9; bool adj[9][9]; // adjacency matrix bool mx[9], my[9]; int cx[9], cy[9]; bool ix[9], iy[9]; // independent set bool match(int x) { for (int y=0; y<Y; ++y) if (adj[x][y] && !my[y]) { my[y] = true; if (cy[y] == -1 || match(cy[y])) { cx[x] = y; cy[y] = x; return true; } } return false; } int maximum_cardinality_bipartite_matching() { memset(cx, -1, sizeof(cx)); memset(cy, -1, sizeof(cy)); int c = 0; for (int x=0; x<X; ++x) { memset(my, false, sizeof(my)); if (match(x)) c++; } return c; } void DFSx(int x) { ix[x] = true; // even distance vertex for (int y=0; y<Y; ++y) if (adj[x][y] && !my[y]) { my[y] = true; if (cy[y] != -1) DFSx(cy[y]); } } void DFSy(int y) { iy[y] = true; // even distance vertex for (int x=0; x<X; ++x) if (adj[x][y] && !mx[x]) { mx[x] = true; if (cx[x] != -1) DFSy(cx[x]); } } void maximum_independent_set() { maximum_cardinality_bipartite_matching(); // 建立X側未匹配點的交錯樹們 memset(ix, false, sizeof(ix)); memset(my, false, sizeof(my)); for (int x=0; x<X; ++x) if (cx[x] == -1) DFSx(x); // 建立Y側未匹配點的交錯樹們 memset(iy, false, sizeof(iy)); memset(mx, false, sizeof(mx)); for (int y=0; y<Y; ++y) if (cy[y] == -1) DFSy(y); // X側未匹配點的交錯樹們＋層層疊疊的交錯環們 for (int x=0; x<X; ++x) if (ix[x] || (cx[x] != -1 && !mx[x] && !my[cx[x]])) cout << "選中X側的第" << x << "點"; // Y側未匹配點的交錯樹們 for (int y=0; y<Y; ++y) if (iy[y]) cout << "選中Y側的第" << y << "點"; }

dominating set

無向圖上，選定數點，其餘點皆與之相鄰，稱作「支配集」。

minimum dominating set [NP-complete]
無向圖上點數最少的dominating set。

minimum dominating set in tree [P]
當給定的圖是樹，得利用DP求解。

minimum dominating set in bipartite graph [NP-complete]
當給定的圖是二分圖。

UVa 10160 1218

edge dominating set

無向圖上，選定數邊，其餘邊皆與之相鄰，稱作「邊支配集」。

minimum edge dominating set [NP-hard]
無向圖上邊數最少的edge dominating set。

independent set與dominating set

independent set
獨立集。選出一些點，互不相鄰。最佳化問題是越多越好。
dominating set
支配集。選出一些點，其餘點皆與之相鄰。最佳化問題是越少越好。

maximal independent set
極大獨立集。無法再選出一些點的獨立集。
maximum independent set
最大獨立集。點數最多的獨立集（點數最多的極大獨立集）。

極大獨立集，必是支配集、必是極小支配集。

極小支配集，不一定是獨立集、不一定是極大獨立集。

延伸閱讀：independent dominating set

「獨立支配集」。既是支配集、又是獨立集。

延伸閱讀：irredundant set

每一個選定的點，至少都有一個只有自己才能支配到的點。自己可以支配自己。

maximal irredundant set = minimal dominating set，一一對應。

vertex cover

一張無向圖上，挑選數個點，碰觸到所有邊，這些點就叫做一個「點覆蓋」，可能有許多種。換句話說，每一條邊，都會碰觸到一個以上的選定點。

點覆蓋，就像是紙鎮，壓住了所有邊，讓邊不會被吹走。

點覆蓋，一個點集合，這些點會是圖上每一條邊，其中一端或兩端的端點。

minimum vertex cover [NP-complete]
一張圖上點數最少的vertex cover。

minimum vertex cover in tree [P]
當給定的圖是樹，得利用greedy method，從樹葉往樹根方向選出節點。

minimum vertex cover in bipartite graph [P]
當給定的圖是二分圖，得化作maximum cardinality bipartite matching解決。

UVa 10243 10859 10984 11419 11095 ICPC 2897

edge cover

一張無向圖上，挑選數條邊，碰觸到所有點，這些邊就叫做一個「邊覆蓋」，可能有許多種。

minimum edge cover [P]
一張圖上邊數最少的edge cover。
得化作maximum matching解決。

minimum edge cover in bipartite graph [P]
當給定的圖是二分圖，得利用greedy method，優先覆蓋degree最小的點。

minimum/maximum weight edge cover [P]
一張圖上權重最小（大）的edge cover。
得化作minimum/minimum weight matching解決。【待補文字】

UVa 10349

minimum edge cover

首先在圖上求得一個maximum matching之後，對於那些單身的點，都由匹配點連過去。如此便形成了minimum edge cover。

packing與covering

一般圖，packing與covering相互對應。

general graph:

|maximum independent set|      + |minimum vertex cover| = |V|
|maximum independent edge set| + |minimum edge cover|   = |V|

各種點獨立集、各種點覆蓋，恰好互補，一一對應。
最大點獨立集、最小點覆蓋，兩者當然也是互補。
各種邊獨立集（匹配）、各種邊覆蓋，沒有互補，沒有一一對應、。
最大邊獨立集（最大匹配）、最小邊覆蓋，兩者幾乎相等，差異是未匹配點所連接的邊。

引入clique。clique、independent set、vertex cover，三者等價，可以互相轉換。

packing與covering in bipartite graph

二分圖，性質更強。König's theorem。

bipartite graph:

|maximum independent set|       = |minimum edge cover|
|maximum independent edge set|  = |minimum vertex cover|

|maximum independent set|      + |minimum vertex cover| = |V|
              +                             +
|maximum independent edge set| + |minimum edge cover|   = |V|
              ||                            ||
             |V|                           |V|

引入biclique。biclique、independent set、vertex cover，三者等價，可以互相轉換。

最佳化問題當中，此三者與edge cover、independent edge set = matching，五者等價，可以互相轉換，都可以套用s-t cut、s-t flow解決。

UVa 11159 12083 12168 ICPC 6309

概論

問題有兩種：packing、covering。
支配元件有兩種：路徑、環。
支配元件限制有兩種：點不重複（邊亦然）、邊不重複。
被支配元件有兩種：所有點、所有邊（點亦然）。
最佳化有四種：支配的路徑數量、路徑長度、單一路徑長度；被支配的點（邊）數量。

總共2×2×2×2×4種組合，並不是全部都具備討論意義。以下列出我遭遇過的組合，也歡迎大家提供其他組合的題目。

packing系列

{minimum cardinality} vertex-disjoint path + vertex + packing
graph [NP-hard] 等同許多條Hamilton path。
tree  [linear]  greedy method。從樹葉往樹根方向選出路徑。
                建立BFS tree。
                以levelorder的逆序拜訪各點。
                如果該點的鄰邊超過二條，
                就隨意留下兩條連往小孩的邊，刪除其餘鄰邊。
DAG   [P]       化作maximum cardinality bipartite matching。
                DAG的邊i->j，對應到二分圖的邊Xi->Yj。
                當匹配數越大，則末端端點越少，則路徑數也越少。

UVa 11381 12831

{maximum/minimum weight} vertex-disjoint path + vertex + packing
graph [NP-hard] 等同許多條hamilton path。
tree  [P]       dynamic programming。從樹葉往樹根方向遞歸。
DAG   [P]       化作maximum weight bipartite matching。

ICPC 4141

{minimum/maximum weight} vertex-disjoint cycle + vertex + packing
Graph   [P]     即是minimum/maximum weight 2-factor。
digraph [P]     化作maximum/minimum weight perfect bipartite matching。
                DAG的邊i->j，對應到二分圖的邊Xi->Yj。

ICPC 3353 7463

{minimum cardinality} edge-disjoint path + edge + packing
graph [P]       等同許多條Euler path。
                無向圖：不斷以奇點作為路徑起點。答案為奇點數目的一半。
                有向圖：出邊多於入邊的點，走向入邊多於出邊的點。

UVa 10248

{minimum/maximum weight} edge-disjoint path + edge + packing
graph [P]      其實就是整張圖所有邊的權重總和。trivial。

{minimum/maximum weight} edge-disjoint cycle + edge + packing
graph [P]      minimum cost flow。

ICPC 4030

covering系列

{minimum cardinality} vertex-disjoint path + edge + covering
graph [P]      minimum s-t flow。源點連至沒有入邊的點，沒有出邊的點連至匯點。

UVa 1440 ICPC 4597