FPT 归约

参数化算法允许组合爆炸集中在小参数 $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 归约的核心承诺只有答案、时间形状与参数界；若还需保留解值、核大小或指数底数，必须使用更强且另行定义的归约。