NP 完全性只说明(若 P≠NP\mathrm P\ne\mathrm{NP})「任意实例、精确最优、多项式时间」三者不可兼得。实践中的实例往往有特殊结构:参数很小、图是一棵树、网络是一个环、图是二分图。利用这些结构,NP 难问题的特殊情形可以被精确且高效地求解。

1. 引入:三者只能取其二

需要求解一个 NP 难问题,该怎么办?

理论告诉我们,不太可能找到多项式时间算法。实践中必须牺牲以下三个目标之一:

放弃最优:近似算法、启发式算法,在多项式时间内给出有质量保证(或至少看起来不错)的解;

放弃多项式:指数时间,但比暴力搜索好得多,例如分支定界、整数规划求解器;

放弃任意实例:只解决实践中出现的特殊情形,在这些情形上做到精确且高效。

本章讨论第三条路。特殊性来自两个方面:参数小(第 2、4 节,复杂度的指数部分只依赖于参数)与结构好(第 3、5 节,树与二分图上问题变得多项式可解)。

2. 参数小:寻找小的顶点覆盖

给定图 G=(V,E)G=(V,E) 与整数 kk,是否存在 S⊆VS\subseteq V,∣S∣≤k|S|\le k,使每条边 (u,v)(u,v) 都满足 u∈Su\in S 或 v∈Sv\in S?

顶点覆盖是 NP 完全的,但实践中 kk 常常很小。暴力算法枚举全部 (nk)=O(nk)\binom nk=O(n^k) 个 kk 元子集,每个用 O(kn)O(kn) 时间检查,共 O(knk+1)O(kn^{k+1})。这在 kk 固定时是多项式,但 kk 出现在 nn 的指数上:k=10, n=1000k=10,\ n=1000 时便完全不可行。目标是 O(f(k)⋅poly(n))O(f(k)\cdot\mathrm{poly}(n)),把指数爆炸限制在参数 kk 上。

设 (u,v)(u,v) 是 GG 的一条边。GG 有大小 ≤k\le k 的顶点覆盖,当且仅当 G−uG-u 与 G−vG-v 中至少有一个有大小 ≤k−1\le k-1 的顶点覆盖。这里 G−uG-u 表示删去 uu 及其关联的边。

(⇒\Rightarrow)设 SS 是 GG 的大小 ≤k\le k 的顶点覆盖。SS 必含 uu 或 vv,不妨设含 uu,则 S−uS-u 是 G−uG-u 的顶点覆盖,大小 ≤k−1\le k-1。

(⇐\Leftarrow)设 SS 是 G−uG-u 的大小 ≤k−1\le k-1 的顶点覆盖,则 S∪{u}S\cup\{u\} 覆盖了 G−uG-u 的全部边以及与 uu 关联的边,是 GG 的大小 ≤k\le k 的顶点覆盖。□\square

若 GG 有大小为 kk 的顶点覆盖,则 GG 至多有 k(n−1)k(n-1) 条边。
每个顶点至多覆盖 n−1n-1 条边。□\square
算法实现
\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}
上述算法在 O(2kkn)O(2^k kn) 时间内判定 GG 是否有大小 ≤k\le k 的顶点覆盖。

正确性由两个引理得到。剪枝后图至多有 knkn 条边,删点、选边等操作耗时 O(kn)O(kn)。设运行时间为 T(n,k)T(n,k),则

T(n,k)≤{cn,k=1,2T(n,k−1)+ckn,k>1, T(n,k)\le\begin{cases}cn, & k=1,\\ 2T(n,k-1)+ckn, & k>1,\end{cases}

归纳可得 T(n,k)≤2kcknT(n,k)\le2^kckn:2⋅2k−1c(k−1)n+ckn=2kckn−2kcn+ckn≤2kckn2\cdot2^{k-1}c(k-1)n+ckn=2^kckn-2^kcn+ckn\le2^kckn(因 k≤2kk\le2^k)。直观地看,递归树是深度 ≤k\le k 的二叉树,至多 2k+12^{k+1} 个结点,每个结点耗时 O(kn)O(kn)。□\square

Fig 1 顶点覆盖的有界搜索树
Fig 1 顶点覆盖的有界搜索树

与暴力的 O(knk+1)O(kn^{k+1}) 相比,2k2^k 不再依赖 nn:k=10k=10 时只是常数 1024。以 n=1000, k=10n=1000,\ k=10 为例,暴力约需 10⋅100011=103410\cdot1000^{11}=10^{34} 步,分支算法约 210⋅10⋅1000≈1072^{10}\cdot10\cdot1000\approx10^7 步,前者永远算不完,后者不到一秒。两者在「kk 固定时都是多项式」这一点上并无区别,区别在于 kk 是否出现在 nn 的指数上。

固定参数可解与核化

运行时间为 f(k)⋅poly(n)f(k)\cdot\mathrm{poly}(n) 的问题称为固定参数可解(FPT)。另一个常用技术是核化:度数 >k>k 的顶点必在任何大小 ≤k\le k 的覆盖中(否则它的 >k>k 个邻居都要选入),可以直接选入并令 k←k−1k\gets k-1;全部度数 ≤k\le k 后,若边数超过 k2k^2 则无解。于是在多项式时间内把问题压缩到 O(k2)O(k^2) 条边的「核」上,再对核做分支,得到 O(kn+2kk2)O(kn+2^kk^2)。目前最好的结果约为 O(1.2738k+kn)O(1.2738^k+kn)。并非所有参数化问题都是 FPT 的:例如以解的大小 kk 为参数的团问题,普遍认为不存在 f(k)⋅poly(n)f(k)\cdot\mathrm{poly}(n) 的算法。

推广:击中集

给定集合 A1,…,Am⊆UA_1,\dots,A_m\subseteq U,每个 ∣Ai∣≤c|A_i|\le c,问是否存在 H⊆UH\subseteq U,∣H∣≤k|H|\le k,与每个 AiA_i 都相交。顶点覆盖是 c=2c=2 的情形(每条边是一个二元集合)。同样的分支:任取一个未被击中的 AiA_i,HH 必含其中某个元素,对它的至多 cc 个元素分别递归,深度 ≤k\le k,得 O(ck⋅kcm)O(c^k\cdot kcm)。

3. 结构好:树上的独立集

给定一棵树,求最大的顶点子集,使其中任意两点之间没有边。

一般图上的独立集是 NP 完全的,但树没有圈,问题大为简化。

事实:至少有两个顶点的树至少有两个叶子;

关键观察:若 vv 是叶子,则存在包含 vv 的最大独立集。

设 (u,v)(u,v) 是一条边,vv 是叶子。则存在包含 vv 的最大独立集。
交换论证。任取最大独立集 SS:若 v∈Sv\in S,结论已成立;若 u∉Su\notin S 且 v∉Sv\notin S,则 S∪{v}S\cup\{v\} 仍是独立集,与 SS 最大矛盾;若 u∈Su\in S 且 v∉Sv\notin S,则 S∪{v}∖{u}S\cup\{v\}\setminus\{u\} 是独立集(vv 唯一的邻居 uu 已被移除),大小不变,也是最大独立集。□\square
下面的贪心算法求出森林(从而树)中的最大独立集。
由引理,存在包含叶子 vv 的最大独立集;该独立集不含 uu,于是在 F−{u,v}F-\{u,v\} 中的部分是 F−{u,v}F-\{u,v\} 的最大独立集(否则可替换得到更大的独立集)。删去 u,vu,v 后仍是森林,对边数归纳即可;没有边时,剩下的孤立点全部加入。□\square
算法实现
\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}

按后序考察结点(孩子先于父亲),每次遇到的未删除的非根结点要么是叶子,要么它的孩子都已被删除,因此可以在 O(n)O(n) 时间内实现。

3.1 带权的情形

给定一棵树与顶点权 wv>0w_v>0,求独立集 SS 使 ∑v∈Swv\sum_{v\in S}w_v 最大。

此时贪心失效:在星形图中,若中心的权重大于所有叶子之和,就不应选叶子。但关键观察可以弱化为:

观察:若 (u,v)(u,v) 是边且 vv 是叶子,则最优解要么包含 uu,要么包含与 uu 相邻的全部叶子。

「要么选 uu,要么不选 uu」提示动态规划。任选根 rr,对每个结点 uu,记 TuT_u 为以 uu 为根的子树:

  • OPTin(u)\mathrm{OPT}_{\mathrm{in}}(u):TuT_u 中包含 uu 的独立集的最大权;
  • OPTout(u)\mathrm{OPT}_{\mathrm{out}}(u):TuT_u 中不包含 uu 的独立集的最大权。

选了 uu,孩子都不能选;不选 uu,每个孩子可选可不选,各子树互不影响:

OPTin(u)=wu+∑v∈children(u)OPTout(v),OPTout(u)=∑v∈children(u)max⁡{OPTin(v),OPTout(v)}. \mathrm{OPT}_{\mathrm{in}}(u)=w_u+\sum_{v\in\mathrm{children}(u)}\mathrm{OPT}_{\mathrm{out}}(v),\qquad \mathrm{OPT}_{\mathrm{out}}(u)=\sum_{v\in\mathrm{children}(u)}\max\{\mathrm{OPT}_{\mathrm{in}}(v),\mathrm{OPT}_{\mathrm{out}}(v)\}.
Fig 2 树上最大权独立集的动态规划
Fig 2 树上最大权独立集的动态规划
上述动态规划在 O(n)O(n) 时间内求出树的最大权独立集。
递推式的正确性如上所述:uu 的各孩子子树之间没有边,只通过 uu 相连,所以一旦确定 uu 的取舍,各子树的问题相互独立。按后序计算,每个结点的值在其孩子之后求出;每条边恰被考察一次,总时间 O(n)O(n)。答案为 max⁡{OPTin(r),OPTout(r)}\max\{\mathrm{OPT}_{\mathrm{in}}(r),\mathrm{OPT}_{\mathrm{out}}(r)\}。□\square
算法实现
\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}

树之所以容易,在于删去一个顶点就把问题分成互不相干的子问题,这与分治如出一辙;一般图中删去一个顶点后各部分仍然纠缠在一起。

顺带得到树上的最小权顶点覆盖:任何图中 SS 是独立集当且仅当 V∖SV\setminus S 是顶点覆盖(见上一章「顶点覆盖、独立集与团」),故最小权顶点覆盖的权等于 ∑vwv\sum_v w_v 减去最大权独立集的权,也是 O(n)O(n)。也可以直接写递推:选 uu 则孩子可选可不选,不选 uu 则每个孩子都必须选(否则边 (u,v)(u,v) 未被覆盖)。第 2 节的参数化算法处理的是「覆盖小」,这里处理的是「图是树」,是同一个 NP 完全问题的两种可解特例。

树宽

把「删去一个顶点就分开」推广为「删去少量顶点就分开」,便得到树分解与树宽:树宽为 ww 的图可以按一棵树的形状组织,每个结点是至多 w+1w+1 个顶点的「袋子」。在袋子上做类似的动态规划,状态数为 2w+12^{w+1},最大权独立集可在 O(2w⋅n)O(2^w\cdot n) 时间内求解。树是树宽为 1 的图。

4. 参数小:环上的圆弧染色

波分复用(WDM)允许 mm 条通信流(弧)共享一段光纤,只要它们使用不同的波长。把波长看作颜色:经过同一段光纤的弧必须染不同颜色,问 kk 种颜色是否够用。

圆弧染色:环形网络有 nn 个结点,给定 mm 条弧(环上的路径),能否用 kk 种颜色给弧染色,使经过同一条边的弧颜色互不相同?

坏消息:即使在环上,这个问题也是 NP 完全的(kk 作为输入的一部分);

暴力:尝试全部 kmk^m 种染色,时间 O(km)O(k^m);

目标:O(f(k)⋅poly(m,n))O(f(k)\cdot\mathrm{poly}(m,n))。实践中波长数 kk 很小,弧数 mm 与结点数 nn 可能很大。

在路径(区间)上,问题由贪心中的区间划分解决:按左端点排序贪心染色,所用颜色数恰为深度(同一位置的最大弧数)。在环上,颜色数 ≥\ge 深度(弱对偶)仍然成立,但等号(强对偶)不再成立。

给出一个环上的例子,深度为 2,但需要 3 种颜色。
取 6 条边 e1,…,e6e_1,\dots,e_6 的环,三条弧 A={e1,e2,e3}A=\{e_1,e_2,e_3\},B={e3,e4,e5}B=\{e_3,e_4,e_5\},C={e5,e6,e1}C=\{e_5,e_6,e_1\}。每条边至多被两条弧经过,深度为 2;但三条弧两两共享一条边(A,BA,B 共享 e3e_3,B,CB,C 共享 e5e_5,C,AC,A 共享 e1e_1),必须染三种不同的颜色。□\square
Fig 3 环上强对偶失效的例子,以及在 $v_0$ 处剪开后的区间
Fig 3 环上强对偶失效的例子,以及在 v0v_0 处剪开后的区间

4.1 从圆弧到区间

设深度 d≤kd\le k(否则显然无解)。选一个结点 v0v_0 作为切点,把环在 v0v_0 处剪开,得到路径 v0,v1,…,vnv_0,v_1,\dots,v_n(vnv_n 是 v0v_0 的另一份拷贝),边为 ei=(vi−1,vi)e_i=(v_{i-1},v_i)。经过切点的弧被切成两段区间:一段从 v0v_0 开始(含 e1e_1),一段在 vnv_n 结束(含 ene_n)。

等价问题:弧可以用 kk 色染色,当且仅当区间可以用 kk 色染色,且每条被切开的弧的两段颜色相同。

不妨通过添加只覆盖一条边的虚拟弧,使每条边恰好被 kk 条弧经过。这不改变可染色性:虚拟弧只与同一条边上的弧冲突,给定原弧的一个 kk 色染色,每条边上尚未用到的颜色恰好够分给那里的虚拟弧;反之删去虚拟弧即可。于是在每条边 eie_i 上,经过它的 kk 条弧的染色就是这 kk 条弧到 kk 种颜色的一个双射。

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}
弧可以 kk 色染色,当且仅当算法返回真;运行时间为 O(k!⋅n)O(k!\cdot n)(忽略 kk 的多项式因子)。

正确性:对 ii 归纳可知,Ci\mathcal C_i 恰为「经过 e1,…,eie_1,\dots,e_i 的区间的某个合法染色、且在 e1e_1 上为 σ0\sigma_0」在 eie_i 上的限制的全体:从 ei−1e_{i-1} 到 eie_i,继续经过的区间颜色不变,新开始的区间只能使用结束的区间释放的颜色,而算法枚举了全部分配方式。在 e1e_1 上固定 σ0\sigma_0 不失一般性:任何合法染色经过颜色置换后都在 e1e_1 上等于 σ0\sigma_0。最后,环的合法染色正是首尾两段颜色一致的区间染色,即 Cn\mathcal C_n 中与 σ0\sigma_0 在被切开的弧上一致的染色。

时间:共 nn 个阶段,每个阶段的瓶颈是枚举相容的染色。经过每条边的区间至多 kk 条,故 ∣Ci∣≤k!|\mathcal C_i|\le k!。□\square

k!k! 只依赖于参数,对小的 kk(例如 k=10k=10)即使结点数 nn 或弧数很大,算法也是实用的。

5. 结构好:二分图的顶点覆盖

一般图上的顶点覆盖是 NP 完全的,但在二分图上可以由最大匹配直接得到。

设 MM 是任意匹配,SS 是任意顶点覆盖,则 ∣M∣≤∣S∣|M|\le|S|。
MM 中的每条边都至少有一个端点在 SS 中,而 MM 中的边两两不共享端点,所以 SS 中的每个顶点至多覆盖 MM 的一条边。□\square

一般图中等号未必成立:三角形的最大匹配为 1,最小顶点覆盖为 2。但在二分图中,强对偶成立:

在二分图中,最大匹配的大小等于最小顶点覆盖的大小。

由弱对偶,只需找到匹配 MM 与顶点覆盖 SS 使 ∣M∣=∣S∣|M|=|S|。

设二分图 G=(L∪R,E)G=(L\cup R,E)。按二分匹配的方式建立流网络:源点 ss 到每个 u∈Lu\in L 连容量为 1 的边,每个 v∈Rv\in R 到汇点 tt 连容量为 1 的边,原图的边 u→vu\to v(u∈L,v∈Ru\in L,v\in R)容量为 ∞\infty。最大流的值等于最大匹配的大小。设 MM 为最大匹配,(A,B)(A,B) 为最小割(s∈A, t∈Bs\in A,\ t\in B),记

LA=L∩A,LB=L∩B,RA=R∩A,RB=R∩B.L_A=L\cap A,\quad L_B=L\cap B,\quad R_A=R\cap A,\quad R_B=R\cap B.

断言 1:S=LB∪RAS=L_B\cup R_A 是顶点覆盖。考虑边 (u,v)∈E(u,v)\in E。若 u∈LAu\in L_A 且 v∈RBv\in R_B,则容量为 ∞\infty 的边 u→vu\to v 从 AA 指向 BB,割容量为无穷,与最小割的容量至多 ∣L∣|L|(割 ({s},V∖{s})(\{s\},V\setminus\{s\}))矛盾。故 u∈LBu\in L_B 或 v∈RAv\in R_A(或两者兼有)。

断言 2:∣S∣=∣M∣|S|=|M|。由最大流最小割定理,∣M∣=cap(A,B)|M|=\mathrm{cap}(A,B)。从 AA 到 BB 的边中,无穷容量的边已被排除,只剩形如 s→us\to u(u∈LBu\in L_B)与 v→tv\to t(v∈RAv\in R_A)的边,各贡献 1,故

∣M∣=cap(A,B)=∣LB∣+∣RA∣=∣S∣.□|M|=\mathrm{cap}(A,B)=|L_B|+|R_A|=|S|.\qquad\square
Fig 4 由最小割读出最小顶点覆盖 $S=L_B\cup R_A$
Fig 4 由最小割读出最小顶点覆盖 S=LB∪RAS=L_B\cup R_A

证明是构造性的:求出最大流后,从 ss 出发在残量网络中可达的顶点即构成最小割的 AA 侧,取 S=LB∪RAS=L_B\cup R_A 便是最小顶点覆盖。因此二分图的最小顶点覆盖可以在多项式时间内求出(用 Ford–Fulkerson 为 O(mn)O(mn));由 V∖SV\setminus S 是独立集,二分图的最大独立集大小为 n−∣M∣n-|M|,也随之可解。

弱对偶的另一个用处:2 倍近似

一般图上强对偶不成立,但弱对偶仍然给出一个简单的近似算法。贪心地求一个极大匹配 MM(不断加入与已选边不相交的边,直到不能再加),取 MM 的全部 2∣M∣2|M| 个端点为 SS。若有边两端都不在 SS 中,它就能加入 MM,与极大性矛盾,故 SS 是顶点覆盖;由弱对偶,∣S∣=2∣M∣≤2 OPT|S|=2|M|\le2\,\mathrm{OPT}。这就是第 1 节「放弃最优」的一条路。在 P≠NP\mathrm P\neq\mathrm{NP} 下,已知不存在 1.361.36 倍的近似算法(Dinur–Safra),而在唯一游戏猜想下,22 倍已是最优。

线性规划的视角

顶点覆盖的线性规划松弛 min⁡∑vxv\min\sum_v x_v,xu+xv≥1 (∀(u,v)∈E)x_u+x_v\ge1\ (\forall(u,v)\in E),x≥0x\ge0 的对偶恰是最大分数匹配。二分图的关联矩阵是全幺模的,两个线性规划都有整数最优解,于是 König–Egerváry 定理就是线性规划强对偶定理的整数版本。一般图中松弛有分数解(三角形上每点取 1/21/2),对偶间隙随之出现,这也是一般图顶点覆盖困难的一种体现。

6. 小结

问题一般情形特殊结构算法复杂度
顶点覆盖NP 完全覆盖大小 kk 小沿边分支 + 剪枝O(2kkn)O(2^kkn)
独立集NP 完全树贪心取叶子O(n)O(n)
带权独立集NP 难树子树 DP(选 / 不选根)O(n)O(n)
圆弧染色NP 完全环,颜色数 kk 小剪开成区间,逐边枚举染色O(k!⋅n)O(k!\cdot n)
顶点覆盖NP 完全二分图最大流 / 最小割多项式

NP 完全性是关于最坏情形、全部实例的论断。面对一个 NP 难问题,与其直接放弃,不如先问:实际实例有什么结构?参数是否很小?图是否像树、像环、是二分图?参数小时,把指数爆炸关进参数里(2k2^k、k!k!);结构好时,问题分解为独立的子问题(树),或者出现强对偶(二分图)。这两种思路分别发展为参数化复杂性与结构图论中的算法,而放弃最优的另一条路则通向近似算法。