FPT 归约

形式陈述 ​

设 $A,B\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ 是参数化问题公理库参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。。many-one FPT 归约是算法 $R$，输入 $(x,k)$ 后输出 $(x^{\prime },k^{\prime })$，满足

$$(x,k)\in A⟺(x^{\prime },k^{\prime })\in B,k^{\prime }\le g(k),$$

并在 $f(k)|x{|}^c$ 时间内完成，其中 $f,g$ 是可计算函数，$c$ 是与 $k$ 无关的常数。输出长度自动受运行时间限制。与经典多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。相比，归约可在参数上付出超多项式的 $f(k)$，但输入规模的指数仍必须固定，且新参数不能偷偷依赖 $|x|$ 无界增长。

FPT 归约传递 fixed-parameter tractability：若 $A{\le }_{\mathrm{fpt}}B$，且 $B$ 可在 $h(k^{\prime })|x^{\prime }{|}^d$ 时间判定，则组合算法以某个只依赖 $k$ 的函数乘 $|x{|}^{O(1)}$ 判定 $A$。归约可复合，因为参数界 $k^{\prime }\le g(k)$ 会在下一步继续变成原参数的函数。

直觉 ​

参数化算法允许组合爆炸集中在小参数 $k$ 上。FPT 归约因此可以对 $k$ 做昂贵预处理，却必须保护这一隔离：目标实例的参数只能由原参数控制，不能把整个输入规模塞进 $k^{\prime }$ 后再宣称目标算法“只对参数指数”。

答案等价保证正确性，参数控制保证可处理性方向，FPT 时间保证翻译本身没有把 $n$ 放到指数里。缺少任何一项，归约都无法稳定传递 FPT 成员资格或 W 层级困难性。

例子与边界 ​

参数化 Clique 到参数化 Independent Set 有直接归约：把图 $G$ 变为补图 $\bar{G}$，保持 $k^{\prime }=k$。$G$ 有大小 $k$ 的 clique，当且仅当 $\bar{G}$ 有大小 $k$ 的独立集；构造补图需多项式时间，参数完全不膨胀。这里保留的是团与独立集公理库团与独立集Clique · Independent set · 团 · 独立集图中两类组内边关系达到全有与全无极端的顶点集合。的结构互补，而不是重新编码一个任意数字阈值。

一个无效“归约”可以把 $k^{\prime }$ 设为 $|x|$，再把原实例原封不动交给一个时间 $2^{k^{\prime }}\mathrm{poly}(|x|)$ 的目标算法。答案或许保持，但组合后仍是普通指数时间；因为不存在只依赖原 $k$ 的 $g$ 控制 $k^{\prime }$，它不是 FPT 归约。

FPT 归约也不必是经典多项式时间：若 $f(k)=2^{2^k}$，定义仍允许它，只要 $n$ 的次数不依赖 $k$。这不意味着归约实用，只表示它在参数化复杂度的闭包意义下合法。用于具体算法传递时，仍应报告 $f,g$ 的真实增长。

推论与应用 ​

FPT 归约组织 W[1] 等参数化困难类，并让已知困难性沿正确方向传播。要证明目标问题参数化困难，应从已知困难问题归约到目标；方向写反只给源问题一个上界，与经典 NP-hardness 论证的逻辑相同。

核化、参数化近似和细粒度归约各自保护不同资源，不可仅因都带参数就互换。FPT 归约的核心承诺只有答案、时间形状与参数界；若还需保留解值、核大小或指数底数，必须使用更强且另行定义的归约。

参考资料

• Rodney G. Downey and Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013, Chs. 1–2.
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015, §2.1, parameterized reductions.