迭代压缩 | Codeboy's Blog

形式陈述

迭代不变量

本页选择一类明确的参数化顶点删除问题：给有限图 $G=(V,E)$ 和整数预算 $k\ge0$ ，要求找 $X\subseteq V$ ，使 $|X|\le k$ 且 $G-X$ 属于图类 $\Pi$ 。假设空图属于 $\Pi$ ，并且 $\Pi$ 对取诱导子图封闭，例如无边图或二分图。若 $k\ge|V|$ ，删除全部顶点就是可行解；下面取 $k<|V|=n$ 。

按顺序 $v_1,\ldots,v_n$ 定义诱导前缀 $G_i=G[\{v_1,\ldots,v_i\}]$ ，从 $G_0$ 和 $X_0=\varnothing$ 开始。已有 $|X_{i-1}|\le k$ 且 $G_{i-1}-X_{i-1}\in\Pi$ 时，

Z=X_{i-1}\cup\{v_i\},\qquad G_i-Z=G_{i-1}-X_{i-1}\in\Pi,

所以 $Z$ 是大小至多 $k+1$ 的可行删除集。若 $|Z|\le k$ ，直接令 $X_i=Z$ ；否则 compression 子程序接收 $(G_i,k,Z)$ ，或者返回大小至多 $k$ 的新删除集，或者正确判定不存在这样的集。外层只在后一种情况下拒绝。

拒绝可以传回完整实例，是因为任何全图解 $Y$ 都会在前缀上留下解 $Y\cap V(G_i)$ ： $G_i-(Y\cap V(G_i))$ 是 $G-Y$ 的诱导子图，仍在 $\Pi$ 中。这个封闭性条件负责“困难前缀意味着困难全图”；对任意非遗传性质，不能直接沿用这个推断。

Disjoint compression

给可行旧删除集 $Z$ ，枚举候选新解 $Y$ 与它的交集 $I=Y\cap Z$ ，至多 $2^{k+1}$ 种； $|I|>k$ 的分支立即丢弃。固定 $I$ 后先从图中删去 $I$ ，强制保留 $Z\setminus I$ ，再寻找

Y'\subseteq V\setminus Z,\qquad |Y'|\le k-|I|, \qquad G-(I\cup Y')\in\Pi.

任何合法 $Y$ 都落在其真实交集对应的分支中，因此完备性保留。每个分支的难度取决于 $\Pi$ ；枚举交集本身尚未解决 disjoint 子问题。

直觉

已有的 $k+1$ 解不是最终答案，而是一份把剩余实例变得有结构的证书。枚举新旧解交集后，一部分旧解点被强制保留、另一部分被强制删除，原问题由此变成 disjoint compression 子问题；若这个受限版本容易，便能逐项扩大实例而始终把解压回大小 $k$ 。

加入新元素得到 k+1 解并经交集划分压缩回 k 解 — 迭代压缩的解扩张与 disjoint compression

例子与边界

Odd Cycle Transversal 图像

已有 $k+1$ 个顶点删除后图为二分图。猜哪些旧删除点仍删，剩下旧点必须重新放回并指定二分图两侧；压缩步骤寻找少量新顶点消除由这些放回点造成的奇环。这是范式的经典来源，不是把数据文件压小。

失败边界

若 compression subproblem 与原问题同样难，外层迭代没有收益。复杂度必须乘 $n$ 次迭代与 $2^{k+1}$ 交集猜测；不能只报一次子程序。可行 $k+1$ 解、起始基例和每轮返回解的归纳链缺一不可。它与核化都属参数化技术，但前者维护解，后者缩减实例。

顶点覆盖的两个小实例

在路径 $a-b-c$ 上取预算 $k=1$ 。前缀 $a-b$ 可用删除集 $\{a\}$ 使剩余图无边；加入 $c$ 后得到旧解 $Z=\{a,c\}$ 。交集分支 $I=\varnothing$ 强制保留 $a,c$ ，它们的外部邻居 $b$ 因而必须删除，返回新解 $\{b\}$ 。新解可以与旧解完全不交。

三角形则展示失败证书。取 $k=1$ 、旧覆盖 $Z=\{a,b\}$ 。 $I=\varnothing$ 时，禁止删除的 $a,b$ 之间仍有边； $I=\{a\}$ 或 $\{b\}$ 时，剩下的旧顶点迫使删除外部点 $c$ ，总共要删两个； $I=Z$ 又已超预算。所有分支失败，恰好证明不存在一顶点覆盖。

推论与应用

从大小 k+1 的可行解压缩到大小 k，并逐个加入输入元素，外层正确性由数学归纳法组织：归纳假设给前缀解，压缩子程序负责扩展一个元素后恢复目标大小。

Vertex Cover 的完整压缩子程序

这里 $\Pi$ 取无边图，删除集就是顶点覆盖。已知 $Z$ 覆盖全部边，所以 $V\setminus Z$ 是独立集。对每个 $I\subseteq Z$ ：

若 $|I|>k$ ，拒绝本分支。
若 $G[Z\setminus I]$ 内有边，拒绝本分支，因为它的两个端点都被禁止删除。
令 $F=N(Z\setminus I)\setminus Z$ 。为覆盖从禁止点出发的边， $F$ 中每个点都必须加入新覆盖。
若 $|I|+|F|\le k$ ，返回 $I\cup F$ ；否则拒绝本分支。

成功分支无需再搜索： $I$ 已覆盖与它相接的边， $Z\setminus I$ 内无边，通往外部的边由 $F$ 覆盖，外部本来就没有边。反过来，任何交集为 $I$ 的新覆盖都必须包含 $F$ ，因此超预算时确实无解。

邻接表模型下，每个分支可在 $O(n+m)$ 次访问内构造并检查， $m=|E|$ ；至多 $n$ 次压缩给出保守总界 $O(2^k n(n+m))$ ，另计参数和输入的读入。已有解大小小于 $k$ 时直接扩展，不必枚举； $n=0$ 返回空集。归纳、交集枚举与每个 disjoint 子程序的完备性共同给出 FPT 算法。

“压缩”改变的是维护的解大小，实例编码仍随前缀增大。对 Odd Cycle Transversal，剩余图需为二分图，必须处理放回旧顶点的两侧选择及其分离约束；上面的邻居强制规则只实现 Vertex Cover 的压缩。

参考资料

Bruce Reed, Kaleigh Smith, Adrian Vetta, Finding Odd Cycle Transversals, Operations Research Letters, 2004.
Marek Cygan et al., Parameterized Algorithms, Springer, 2015.

形式陈述 ​

迭代不变量 ​

Disjoint compression ​

Odd Cycle Transversal 图像 ​

失败边界 ​

顶点覆盖的两个小实例 ​

Vertex Cover 的完整压缩子程序 ​