domination

domination

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

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

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

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

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

independent set

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。

maximum independent Set in bipartite graph

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

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

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

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

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

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

dominating set

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

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

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

path domination

概論

問題有兩種: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