NP 完全性只说明(若 )「任意实例、精确最优、多项式时间」三者不可兼得。实践中的实例往往有特殊结构:参数很小、图是一棵树、网络是一个环、图是二分图。利用这些结构,NP 难问题的特殊情形可以被精确且高效地求解。
1. 引入:三者只能取其二
需要求解一个 NP 难问题,该怎么办?
理论告诉我们,不太可能找到多项式时间算法。实践中必须牺牲以下三个目标之一:
放弃最优:近似算法、启发式算法,在多项式时间内给出有质量保证(或至少看起来不错)的解;
放弃多项式:指数时间,但比暴力搜索好得多,例如分支定界、整数规划求解器;
放弃任意实例:只解决实践中出现的特殊情形,在这些情形上做到精确且高效。
本章讨论第三条路。特殊性来自两个方面:参数小(第 2、4 节,复杂度的指数部分只依赖于参数)与结构好(第 3、5 节,树与二分图上问题变得多项式可解)。
2. 参数小:寻找小的顶点覆盖
给定图 与整数 ,是否存在 ,,使每条边 都满足 或 ?
顶点覆盖是 NP 完全的,但实践中 常常很小。暴力算法枚举全部 个 元子集,每个用 时间检查,共 。这在 固定时是多项式,但 出现在 的指数上: 时便完全不可行。目标是 ,把指数爆炸限制在参数 上。
设 是 的一条边。 有大小 的顶点覆盖,当且仅当 与 中至少有一个有大小 的顶点覆盖。这里 表示删去 及其关联的边。
()设 是 的大小 的顶点覆盖。 必含 或 ,不妨设含 ,则 是 的顶点覆盖,大小 。
()设 是 的大小 的顶点覆盖,则 覆盖了 的全部边以及与 关联的边,是 的大小 的顶点覆盖。
若 有大小为 的顶点覆盖,则 至多有 条边。
每个顶点至多覆盖 条边。
算法实现
\begin{algorithm}
\caption{Vertex-Cover:判定是否有大小 $\le k$ 的顶点覆盖}
\begin{algorithmic}
\PROCEDURE{VertexCover}{$G, k$}
\IF{$G$ 没有边}
\RETURN \TRUE
\ELIF{$k = 0$ \OR $G$ 有 $\ge kn$ 条边}
\RETURN \FALSE \COMMENT{剪枝引理}
\ENDIF
\STATE 任取 $G$ 的一条边 $(u, v)$
\STATE $a \gets$ \CALL{VertexCover}{$G - u, k - 1$}
\STATE $b \gets$ \CALL{VertexCover}{$G - v, k - 1$}
\RETURN $a \vee b$ \COMMENT{分支引理}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}上述算法在 时间内判定 是否有大小 的顶点覆盖。
正确性由两个引理得到。剪枝后图至多有 条边,删点、选边等操作耗时 。设运行时间为 ,则
归纳可得 :(因 )。直观地看,递归树是深度 的二叉树,至多 个结点,每个结点耗时 。
与暴力的 相比, 不再依赖 : 时只是常数 1024。以 为例,暴力约需 步,分支算法约 步,前者永远算不完,后者不到一秒。两者在「 固定时都是多项式」这一点上并无区别,区别在于 是否出现在 的指数上。
固定参数可解与核化
运行时间为 的问题称为固定参数可解(FPT)。另一个常用技术是核化:度数 的顶点必在任何大小 的覆盖中(否则它的 个邻居都要选入),可以直接选入并令 ;全部度数 后,若边数超过 则无解。于是在多项式时间内把问题压缩到 条边的「核」上,再对核做分支,得到 。目前最好的结果约为 。并非所有参数化问题都是 FPT 的:例如以解的大小 为参数的团问题,普遍认为不存在 的算法。
推广:击中集
给定集合 ,每个 ,问是否存在 ,,与每个 都相交。顶点覆盖是 的情形(每条边是一个二元集合)。同样的分支:任取一个未被击中的 , 必含其中某个元素,对它的至多 个元素分别递归,深度 ,得 。
3. 结构好:树上的独立集
给定一棵树,求最大的顶点子集,使其中任意两点之间没有边。
一般图上的独立集是 NP 完全的,但树没有圈,问题大为简化。
事实:至少有两个顶点的树至少有两个叶子;
关键观察:若 是叶子,则存在包含 的最大独立集。
设 是一条边, 是叶子。则存在包含 的最大独立集。
交换论证。任取最大独立集 :若 ,结论已成立;若 且 ,则 仍是独立集,与 最大矛盾;若 且 ,则 是独立集( 唯一的邻居 已被移除),大小不变,也是最大独立集。
下面的贪心算法求出森林(从而树)中的最大独立集。
由引理,存在包含叶子 的最大独立集;该独立集不含 ,于是在 中的部分是 的最大独立集(否则可替换得到更大的独立集)。删去 后仍是森林,对边数归纳即可;没有边时,剩下的孤立点全部加入。
算法实现
\begin{algorithm}
\caption{Independent-Set-In-A-Forest}
\begin{algorithmic}
\PROCEDURE{IndependentSetForest}{$F$}
\STATE $S \gets \emptyset$
\WHILE{$F$ 至少有一条边}
\STATE 取边 $e = (u, v)$,其中 $v$ 是叶子
\STATE 将 $v$ 加入 $S$
\STATE 从 $F$ 中删去 $u$、$v$ 及与它们关联的所有边
\ENDWHILE
\STATE 将 $F$ 中剩余的(孤立)顶点全部加入 $S$
\RETURN $S$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}按后序考察结点(孩子先于父亲),每次遇到的未删除的非根结点要么是叶子,要么它的孩子都已被删除,因此可以在 时间内实现。
3.1 带权的情形
给定一棵树与顶点权 ,求独立集 使 最大。
此时贪心失效:在星形图中,若中心的权重大于所有叶子之和,就不应选叶子。但关键观察可以弱化为:
观察:若 是边且 是叶子,则最优解要么包含 ,要么包含与 相邻的全部叶子。
「要么选 ,要么不选 」提示动态规划。任选根 ,对每个结点 ,记 为以 为根的子树:
- : 中包含 的独立集的最大权;
- : 中不包含 的独立集的最大权。
选了 ,孩子都不能选;不选 ,每个孩子可选可不选,各子树互不影响:
上述动态规划在 时间内求出树的最大权独立集。
递推式的正确性如上所述: 的各孩子子树之间没有边,只通过 相连,所以一旦确定 的取舍,各子树的问题相互独立。按后序计算,每个结点的值在其孩子之后求出;每条边恰被考察一次,总时间 。答案为 。
算法实现
\begin{algorithm}
\caption{Weighted-Independent-Set-In-A-Tree}
\begin{algorithmic}
\PROCEDURE{WeightedIndependentSetTree}{$T, w$}
\STATE 以某个结点 $r$ 为根
\FORALL{按后序排列的结点 $u$}
\IF{$u$ 是叶子}
\STATE $M_{\mathrm{in}}[u] \gets w_u$,$M_{\mathrm{out}}[u] \gets 0$
\ELSE
\STATE $M_{\mathrm{in}}[u] \gets w_u + \sum_{v \in \mathrm{children}(u)} M_{\mathrm{out}}[v]$
\STATE $M_{\mathrm{out}}[u] \gets \sum_{v \in \mathrm{children}(u)} \max\{M_{\mathrm{in}}[v], M_{\mathrm{out}}[v]\}$
\ENDIF
\ENDFOR
\RETURN $\max\{M_{\mathrm{in}}[r], M_{\mathrm{out}}[r]\}$ \COMMENT{回溯取舍可得独立集本身}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}树之所以容易,在于删去一个顶点就把问题分成互不相干的子问题,这与分治如出一辙;一般图中删去一个顶点后各部分仍然纠缠在一起。
顺带得到树上的最小权顶点覆盖:任何图中 是独立集当且仅当 是顶点覆盖(见上一章「顶点覆盖、独立集与团」),故最小权顶点覆盖的权等于 减去最大权独立集的权,也是 。也可以直接写递推:选 则孩子可选可不选,不选 则每个孩子都必须选(否则边 未被覆盖)。第 2 节的参数化算法处理的是「覆盖小」,这里处理的是「图是树」,是同一个 NP 完全问题的两种可解特例。
树宽
把「删去一个顶点就分开」推广为「删去少量顶点就分开」,便得到树分解与树宽:树宽为 的图可以按一棵树的形状组织,每个结点是至多 个顶点的「袋子」。在袋子上做类似的动态规划,状态数为 ,最大权独立集可在 时间内求解。树是树宽为 1 的图。
4. 参数小:环上的圆弧染色
波分复用(WDM)允许 条通信流(弧)共享一段光纤,只要它们使用不同的波长。把波长看作颜色:经过同一段光纤的弧必须染不同颜色,问 种颜色是否够用。
圆弧染色:环形网络有 个结点,给定 条弧(环上的路径),能否用 种颜色给弧染色,使经过同一条边的弧颜色互不相同?
坏消息:即使在环上,这个问题也是 NP 完全的( 作为输入的一部分);
暴力:尝试全部 种染色,时间 ;
目标:。实践中波长数 很小,弧数 与结点数 可能很大。
在路径(区间)上,问题由贪心中的区间划分解决:按左端点排序贪心染色,所用颜色数恰为深度(同一位置的最大弧数)。在环上,颜色数 深度(弱对偶)仍然成立,但等号(强对偶)不再成立。
给出一个环上的例子,深度为 2,但需要 3 种颜色。
取 6 条边 的环,三条弧 ,,。每条边至多被两条弧经过,深度为 2;但三条弧两两共享一条边( 共享 , 共享 , 共享 ),必须染三种不同的颜色。
4.1 从圆弧到区间
设深度 (否则显然无解)。选一个结点 作为切点,把环在 处剪开,得到路径 ( 是 的另一份拷贝),边为 。经过切点的弧被切成两段区间:一段从 开始(含 ),一段在 结束(含 )。
等价问题:弧可以用 色染色,当且仅当区间可以用 色染色,且每条被切开的弧的两段颜色相同。
不妨通过添加只覆盖一条边的虚拟弧,使每条边恰好被 条弧经过。这不改变可染色性:虚拟弧只与同一条边上的弧冲突,给定原弧的一个 色染色,每条边上尚未用到的颜色恰好够分给那里的虚拟弧;反之删去虚拟弧即可。于是在每条边 上,经过它的 条弧的染色就是这 条弧到 种颜色的一个双射。
4.2 动态规划
算法实现
\begin{algorithm}
\caption{Circular-Arc-Coloring}
\begin{algorithmic}
\PROCEDURE{CircularArcColoring}{$n$ 个结点的环, 弧集, $k$}
\STATE 在切点 $v_0$ 处剪开,被切开的弧成为两段区间
\STATE 给经过第一条边 $e_1$ 的 $k$ 条区间指定 $k$ 种不同的颜色,记此染色为 $\sigma_0$
\STATE $\mathcal C_1 \gets \{\sigma_0\}$ \COMMENT{$\mathcal C_i$:经过 $e_i$ 的区间的全部相容染色}
\FOR{$i \gets 2$ \TO $n$}
\STATE $\mathcal C_i \gets \emptyset$
\FORALL{$\sigma \in \mathcal C_{i-1}$}
\STATE 在结点 $v_{i-1}$ 处结束的区间释放其颜色
\FORALL{将释放的颜色分配给在 $v_{i-1}$ 处开始的区间的方式}
\STATE 将所得染色加入 $\mathcal C_i$ \COMMENT{继续经过的区间保持原颜色}
\ENDFOR
\ENDFOR
\ENDFOR
\IF{存在 $\sigma \in \mathcal C_n$,使每条被切开的弧在 $\sigma$ 中的颜色与在 $\sigma_0$ 中相同}
\RETURN \TRUE
\ENDIF
\RETURN \FALSE
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}弧可以 色染色,当且仅当算法返回真;运行时间为 (忽略 的多项式因子)。
正确性:对 归纳可知, 恰为「经过 的区间的某个合法染色、且在 上为 」在 上的限制的全体:从 到 ,继续经过的区间颜色不变,新开始的区间只能使用结束的区间释放的颜色,而算法枚举了全部分配方式。在 上固定 不失一般性:任何合法染色经过颜色置换后都在 上等于 。最后,环的合法染色正是首尾两段颜色一致的区间染色,即 中与 在被切开的弧上一致的染色。
时间:共 个阶段,每个阶段的瓶颈是枚举相容的染色。经过每条边的区间至多 条,故 。
只依赖于参数,对小的 (例如 )即使结点数 或弧数很大,算法也是实用的。
5. 结构好:二分图的顶点覆盖
一般图上的顶点覆盖是 NP 完全的,但在二分图上可以由最大匹配直接得到。
设 是任意匹配, 是任意顶点覆盖,则 。
中的每条边都至少有一个端点在 中,而 中的边两两不共享端点,所以 中的每个顶点至多覆盖 的一条边。
一般图中等号未必成立:三角形的最大匹配为 1,最小顶点覆盖为 2。但在二分图中,强对偶成立:
在二分图中,最大匹配的大小等于最小顶点覆盖的大小。
由弱对偶,只需找到匹配 与顶点覆盖 使 。
设二分图 。按二分匹配的方式建立流网络:源点 到每个 连容量为 1 的边,每个 到汇点 连容量为 1 的边,原图的边 ()容量为 。最大流的值等于最大匹配的大小。设 为最大匹配, 为最小割(),记
断言 1: 是顶点覆盖。考虑边 。若 且 ,则容量为 的边 从 指向 ,割容量为无穷,与最小割的容量至多 (割 )矛盾。故 或 (或两者兼有)。
断言 2:。由最大流最小割定理,。从 到 的边中,无穷容量的边已被排除,只剩形如 ()与 ()的边,各贡献 1,故
证明是构造性的:求出最大流后,从 出发在残量网络中可达的顶点即构成最小割的 侧,取 便是最小顶点覆盖。因此二分图的最小顶点覆盖可以在多项式时间内求出(用 Ford–Fulkerson 为 );由 是独立集,二分图的最大独立集大小为 ,也随之可解。
弱对偶的另一个用处:2 倍近似
一般图上强对偶不成立,但弱对偶仍然给出一个简单的近似算法。贪心地求一个极大匹配 (不断加入与已选边不相交的边,直到不能再加),取 的全部 个端点为 。若有边两端都不在 中,它就能加入 ,与极大性矛盾,故 是顶点覆盖;由弱对偶,。这就是第 1 节「放弃最优」的一条路。在 下,已知不存在 倍的近似算法(Dinur–Safra),而在唯一游戏猜想下, 倍已是最优。
线性规划的视角
顶点覆盖的线性规划松弛 ,, 的对偶恰是最大分数匹配。二分图的关联矩阵是全幺模的,两个线性规划都有整数最优解,于是 König–Egerváry 定理就是线性规划强对偶定理的整数版本。一般图中松弛有分数解(三角形上每点取 ),对偶间隙随之出现,这也是一般图顶点覆盖困难的一种体现。
6. 小结
| 问题 | 一般情形 | 特殊结构 | 算法 | 复杂度 |
|---|---|---|---|---|
| 顶点覆盖 | NP 完全 | 覆盖大小 小 | 沿边分支 + 剪枝 | |
| 独立集 | NP 完全 | 树 | 贪心取叶子 | |
| 带权独立集 | NP 难 | 树 | 子树 DP(选 / 不选根) | |
| 圆弧染色 | NP 完全 | 环,颜色数 小 | 剪开成区间,逐边枚举染色 | |
| 顶点覆盖 | NP 完全 | 二分图 | 最大流 / 最小割 | 多项式 |
NP 完全性是关于最坏情形、全部实例的论断。面对一个 NP 难问题,与其直接放弃,不如先问:实际实例有什么结构?参数是否很小?图是否像树、像环、是二分图?参数小时,把指数爆炸关进参数里(、);结构好时,问题分解为独立的子问题(树),或者出现强对偶(二分图)。这两种思路分别发展为参数化复杂性与结构图论中的算法,而放弃最优的另一条路则通向近似算法。