参数化复杂度类 FPT

FPT 把组合爆炸隔离到参数 $k$：允许参数部分非常昂贵，却要求数据规模只承担固定次数的多项式成本，即运行时间写成 $f(k)n^{O(1)}$，且关于输入规模的指数必须是与 $k$ 无关的常数。这使算法在小参数、大实例场景中仍可扩展，但不要求 $f$ 温和；$2^{2^k}{n}^2$ 形式上仍属 FPT。与简单地说“固定 $k$ 后是多项式”相比，这个统一形式排除了 $n^k$ 一类指数随参数增长的算法。

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

参数选择决定结论：同一实例按解大小、树宽或数值范围参数化会得到不同问题。FPT 是最坏情况渐近性质；当 $k$ 接近 $n$ 或 $f(k)$ 极大时，理论可处理性不保证工程优势。

参数化问题公理库参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。提供二元输入，时间复杂度公理库时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。中的指数分离给出 FPT 定义。有界搜索树、颜色编码与树宽上的动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。是算法路线；核化公理库核化Kernelization · Problem kernel在总输入多项式时间内把参数化实例约化为大小只依赖参数的等价实例。刻画受参数控制的预处理，FPT 归约公理库FPT 归约FPT reduction · Parameterized reduction在 f(k)|x|^{O(1)} 时间内保持答案，并把目标参数限制为原参数函数的参数化 many-one 归约。传递成员关系，W[1公理库W 层级与 W[1]W hierarchy · W[1]以加权常深电路可满足性和大扇入门层数组织参数化困难性的 W 层级。] 提供条件困难性证据。后三者均为围绕 FPT 的独立概念，不反向加入本页 requires。