核化

形式陈述 ​

对参数化问题公理库参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。 $Q\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$，核化算法在 $(x,k)$ 上以 $(|x|+k{)}^{O(1)}$ 时间输出 $(x^{\prime },k^{\prime })$，满足

$$(x,k)\in Q⟺(x^{\prime },k^{\prime })\in Q,|x^{\prime }|+k^{\prime }\le g(k),$$

其中 $g$ 是可计算函数。输出称为 kernel；若 $g$ 是 $k$ 的多项式，则称 polynomial kernel。标准 kernel 输出仍属于同一问题；允许输出到另一问题或任意短字符串时分别称 generalized kernel 或 compression，不能无标记混用。

对可判定参数化问题，存在某个可计算大小 kernel 当且仅当问题属于 FPT公理库参数化复杂度类 FPTFixed-parameter tractable · FPT可在 f(k)n^O(1) 时间内求解的参数化问题类。。反向方向：先多项式核化，再用任意判定算法解决大小至多 $g(k)$ 的有限核，后段成本只依赖 $k$。正向方向：若 FPT 算法时间为 $f(k)n^c$，当 $n>f(k)$ 时可在 $n^{c+1}$ 时间直接判定并输出固定 yes/no 实例；否则原实例自身大小已由 $f(k)$ 控制。该等价不保证 polynomial kernel。

直觉 ​

核化把参数无关的冗余在正式求解前删掉，只留下由 $k$ 控制的组合核心。每条化简规则都必须保持 yes/no 等价，所有规则结束后还需一个全局大小证明；“实验上变小”不是 kernel bound。

预处理时间必须是总输入多项式，而不只是 $f(k)n^{O(1)}$。否则任何 FPT 求解器都可被重新命名为“预处理”，核化就失去独立意义。

例子与边界 ​

参数化Vertex Cover公理库顶点覆盖Vertex cover与每条边至少一个端点相交的顶点子集。可用高次数规则得到 $O(k^2)$ kernel。若顶点 $v$ 的度大于 $k$，任何大小至多 $k$ 的覆盖都必须含 $v$；否则需选择其超过 $k$ 个邻居。于是删除 $v$ 及其关联边，并把参数减一。

规则耗尽后最大度至多 $k$。若仍有超过 $k^2$ 条边，任意 $k$ 个顶点最多覆盖 $k^2$ 条边，可立即输出固定 no 实例；否则删除孤立点后非孤立顶点至多 $2k^2$。这给出等价性与大小界两个闭环，而非只列“删除高次数点”的步骤。

FPT 并不自动意味着 polynomial kernel；它只通过上述定理给某个可能增长极快的可计算 $g(k)$。反之，一个核很小也不代表实际求解容易，核上仍可能需要指数于 $k$ 的精确算法。

推论与应用 ​

核化是参数化预处理的形式语言，可用于顶点覆盖、反馈点集和各种删除问题。规则设计常结合强制选择、支配关系和局部替换，最终以参数函数界定剩余元素数。

Polynomial-kernel 下界需要 OR-composition、cross-composition 等额外复杂度工具；单凭 W[1]-hardness 不能得出“没有多项式核”。成员资格、FPT 时间与核大小是三种不同结论。

参考资料

• Marek Cygan et al., Parameterized Algorithms, Springer, 2015, Chs. 2–3.
• Rodney G. Downey and Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013, Ch. 2.