迭代压缩

迭代不变量 ​

按 $v_1,\dots ,v_n$ 逐个加入实例。假设已为前 $i-1$ 个元素找到大小至多 $k$ 的删除解 $X$；加入 $v_i$ 后，$X\cup \{v_i\}$ 是新实例大小至多 $k+1$ 的可行解。compression subroutine 接收实例和这份 $k+1$ 解，决定是否存在大小 $k$ 解并返回它。小于等于 $k+1$ 的起始实例有平凡删除解，归纳由此启动。

Disjoint compression ​

给旧解 $X$，猜新解 $Y$ 与 $X$ 的交集 $I$，至多 $2^{k+1}$ 种。固定 $I$ 后强制保留 $X\setminus I$，并在剩余实例中寻找与 $X\setminus I$ 不交、大小至多 $k-|I|$ 的修复集。许多删除问题在“旧解顶点禁止再删”后获得额外结构，才使压缩子问题比原问题容易。

Odd Cycle Transversal 图像 ​

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

失败边界 ​

若 compression subproblem 与原问题同样难，外层迭代没有收益。复杂度必须乘 $n$ 次迭代与 $2^{k+1}$ 交集猜测；不能只报一次子程序。可行 $k+1$ 解、起始基例和每轮返回解的归纳链缺一不可。它与核化公理库核化Kernelization · Problem kernel在总输入多项式时间内把参数化实例约化为大小只依赖参数的等价实例。都属参数化技术，但前者维护解，后者缩减实例。

Vertex Cover 的 disjoint 步 ​

若 $X$ 是大小 $k+1$ 的旧 vertex cover，则 $V\setminus X$ 是独立集。猜 $I=Y\cap X$ 后，要求新 cover $Y$ 与 $X\setminus I$ 不交；因此所有从 $X\setminus I$ 指向 $V\setminus X$ 的邻居都被强制加入 $Y$。检查这些强制点加 $I$ 是否覆盖全部边且大小不超 $k$，给出一个可直接验证的 compression subroutine。

这个例子也说明枚举交集不是形式动作：固定哪些旧解点保留/放回后，剩余结构变成独立集邻接约束，才比原 Vertex Cover 简单。

Vertex Cover 的 disjoint 压缩 ​

已知图 $G_i$ 有大小 $k+1$ 的顶点覆盖 $Z$，目标找大小 $k$ 的新覆盖 $S$。枚举交集 $Y=S\cap Z$ 后，$Z\setminus Y$ 必须不在 $S$ 中；为覆盖它们之间以及它们连向外部的边，所有 $N(Z\setminus Y)\setminus Z$ 都被迫加入 $S$。

一次分支的状态检查为：

1. 验证 $Y$ 覆盖 $G[Z]$ 中没有被强制端点覆盖的边；
2. 构造被迫集合 $F=N(Z\setminus Y)\setminus Z$；
3. 若 $|Y|+|F|>k$ 立即剪枝；
4. 检查 $Y\cup F$ 是否覆盖全部边，或把剩余实例交给 disjoint 子程序。

共有 $2^{k+1}$ 种交集猜测，每个分支做多项式工作，形成 FPT 界。关键不变量是处理第 $i$ 个顶点前已有 $G_{i-1}$ 的大小 $k$ 解，加上新顶点自然得到 $G_i$ 的大小 $k+1$ 解；若初始小实例都没有这份较大解，压缩过程无从启动。

“压缩”指解大小从 $k+1$ 降到 $k$，不改变输入编码长度。对 Odd Cycle Transversal 等问题，disjoint 子问题结构更复杂，不能把 Vertex Cover 的邻居强制规则照搬。

参考资料

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