Question

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，请参考本站文件“ Clique ”。

Maximum Independent Set in Tree

以边边角角的点作为最大独立集，似乎还不错。

在树上，边边角角的点就是树叶。运用 Divide and Conquer，观察树叶及其邻点，将问题分割成四种情况：

一、树叶与父亲都是最大独立集：不成立。
二、树叶与父亲都不是最大独立集：那不如採用三或四，独立集更大。
三、树叶是，父亲不是：可以一试。
四、树叶不是，父亲是：可以一试。

以树叶作为最大独立集，不但填装比较多点，而且剩馀的图比较大张、得以填装更多点！

于是发现了一个 Greedy 演算法：由树叶往树根方向选出独立集，儘量选择树叶，最后就得到最大独立集。不过这种方式无法得到字典顺序最小的最大独立集。

时间複杂度等同于一次 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 演算法，从树叶往树根方向选出节点。

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 演算法，优先覆盖 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。从树叶往树根方向选出路径。
                建立 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 Trail。
                无向图：不断以奇点作为路径起点。答案为奇点数目的一半。
                有向图：出边多于入边的点，走向入边多于出边的点。

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

Cycle Double Cover Conjecture

http://en.wikipedia.org/wiki/Cycle_double_cover