点覆盖问题（Vertex Cover）

rqoi031 · 2023-08-19 13:14:47 · 算法·理论

1. 问题描述

给出一个无向图 G 和一个整数 k，问能否找到一个集合 X\subseteq V(G)，使得 G 中的所有边都有至少一个端点在 X 中。

2. 点覆盖问题

定理1 最小点覆盖可以在 O\left(2^{|V(G)|}\cdot|E(G)|\right) 时间复杂度内计算出。

证明 略。

定义2 \mathcal O^\star(f(n))=O\big(f(n)\cdot poly(\text{input size})\big)。

我们将在下面的分析中忽略多项式系数（几乎），因为它们无关紧要：O(2^nn^{100})\leq O(2.0001^n)。

3. 固定参数可计算

假设我们想要找到一个大小不大于 k 的点覆盖，比如 k=20。于是我们可以使用其他方法而不是找出 V(G) 的所有大小 \leq k 的子集。

定理3 我们可以在 \mathcal O^\star(2^k) 的时间复杂度内解决上面这个问题。

证明 对于每一条边，一定有一个端点在点覆盖中，所以我们可以枚举这两种情况。每次我们找到任意一条没有被覆盖的边，尝试选择它的其中一个端点并递归求解。伪代码：

定义4 对于一个参数问题 P=(L,\kappa)，若存在可计算函数 f(\cdot)，使得对于任意 P 的实例 (x,k=\kappa(x)) 可在 O(f(k)\cdot poly(|x|)) 内求解，则称 P 是固定参数可计算（fixed parameter tractable，FPT）的。

上面定义中的参数 \kappa 可以是输入的任意函数。例如，它可以是解的大小或图的某些度量。其功能是在问题的复杂度中找到指数部分，并将它们（通过乘法）从输入的大小（多项式部分）中分离出来。当参数有界时，我们可以快速解决问题（对于固定参数，在多项式时间内）。

推论5 点覆盖问题对于点覆盖大小是 FPT 的。

比较上面两种算法，第一种时间复杂度为 O\left(\binom{n}{k}\right)，而第二种为 O(2^kn)。我们可以根据 n,k 和一个常数 \alpha 选择其中一种：

尝试分析这个算法的时间复杂度。若 \alpha=\frac{3}{4}，对于第一种情况，有 \mathcal O^\star\left(2^k\right)\leq \mathcal O^\star\left(2^{\frac{3}{4}n}\right)；对于第二种情况，有 \mathcal O^\star\left(\binom{n}{k}\right)\leq\mathcal O^\star\left(\binom{n}{\frac{3}{4}n}\right)。

根据斯特林公式 n!=\Theta\left(\left(\dfrac{n}{e}\right)^{n}\sqrt{2\pi n}\right)，有

这明显比 \mathcal O^\star(2^n) 优。当 \alpha=0.773 时，甚至可以得到 \mathcal O^\star(1.709^n)。

4. 优化

定义6 \forall u\in V(G),N(u)=\big\{v\in V(G)\setminus\{u\}:(u,v)\in E(G)\big\}

考虑换一种思路。对于一个点 u，如果它没有在最小点覆盖里，那么与它相邻的所有点都应在最小点覆盖里。

此外，如果图 G 中的所有点的度数都 \leq 2，我们显然可以 O(|V(G)|) 计算最小点覆盖。

于是，我们得到了一种新的算法：

令 n=|V(G)|，那么时间复杂度 T(n)=T(n-1)+T(n-4)。我们想要找到一个 x 满足 T(n)\leq x^n，也就是 x^n=x^{n-1}+x^{n-4}，解方程 1=\frac{1}{x}+\frac{1}{x^4} 得 x\approx 1.3803。

稍微优化一下：

时间复杂度变成了 \mathcal O^\star(1.3246^n)（证明略）。

5. 其他解法

目前（2022），最小点覆盖的最优解法时间复杂度为 \mathcal O^\star(2^{0.288n})\leq\mathcal O^\star(1.23^n)：A measure & conquer approach for the analysis of exact algorithms (2009)；

最优的 FPT 解法时间复杂度为 O(1.2738^k+kn)：Improved upper bounds for vertex cover (2010)。

6. 参考