形式陈述

参数化问题 $Q$$Q$ 属于固定参数可解类 $\mathrm{FPT}$$\mathrm{FPT}$，若存在可计算函数 $f$$f$、常数 $c$$c$ 和算法，使实例 $(x,k)$$(x,k)$ 可在

$$ f(k)\,|x|^c $$$$f(k)|x{|}^c$$

时间内判定，其中指数 $c$$c$ 与 $k$$k$ 无关。空间界需另行说明。相比之下，$|x|^{f(k)}$$|x{|}^{f(k)}$ 只给出 XP 算法；两者都对每个固定 $k$$k$ 为多项式，但 FPT 把组合爆炸从输入规模的指数中分离出来。

直觉

允许参数部分非常昂贵，却要求数据规模只承担固定次数的多项式成本；这使算法在小参数、大实例场景中仍可扩展。

例子与边界

顶点覆盖可按任一未覆盖边 $(u,v)$$(u,v)$ 分支选择 $u$$u$ 或 $v$$v$，得到 $O(2^k(n+m))$$O(2^k(n+m))$ 时间，因此属于 FPT。枚举全部 $k$$k$ 元顶点子集的 $O(n^k)$$O(n^k)$ 算法仅证明属于 XP。$f(k)$$f(k)$ 必须可计算，但定义不要求它是单指数；实际算法质量仍高度依赖其增长率。

推论与应用

FPT 算法常由有界搜索树、动态规划、颜色编码、迭代压缩和核化获得。参数化归约与 W[1]-hardness 用于解释为何某些 $n^k$$n^k$ 算法难以改造成 $f(k)n^{O(1)}$$f(k)n^{O(1)}$。

参考资料

• Rodney G. Downey and Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013，Chs. 1–3, fixed-parameter tractability and basic techniques。
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015，Chs. 1–2, FPT, XP, and branching algorithms。