参数化复杂度类 FPT

为什么 $N^k$ 还没有给出 FPT 算法 ​

比较下面两种界：

当输入长度放大十倍、参数不变时，第一种开销放大 $100$ 倍；第二种则放大 ${10}^k$ 倍。$N^k$ 把参数放进输入规模的指数，因而只给出 XP 型算法。两者对每个固定 $k$ 都是多项式，但只有前一种明确满足 FPT 的统一形式。

这里是在判断算法上界，不是给问题贴永久标签。发现一个 $N^k$ 算法，并不能证明问题不属于 FPT；它也许还有一个尚未采用的 $2^k{N}^2$ 算法。另一方面，$f(k)$ 可以增长得非常快，$2^{2^k}{N}^2$ 也符合定义。FPT 描述一种最坏情况结构，不等于参数依赖已经足够好。

顶点覆盖：一条边迫使两选一 ​

给定简单无向图 $G=(V,E)$ 和非负整数参数 $k$，询问是否能选至多 $k$ 个顶点，使每条边至少有一个端点被选中。这就是按解大小参数化的顶点覆盖。

任取一条仍未覆盖的边 $\{u,v\}$。任何合法解都必须包含 $u$ 或 $v$，于是只需两条分支：选择 $u$ 并删去它覆盖的边，或者选择 $v$ 并删去它覆盖的边；两条分支都把剩余预算减一。

                 未覆盖边 {u,v}
                  /          \
             选择 u          选择 v
             预算 k−1        预算 k−1

当边全部消失时成功；当预算已经为零而仍有边时失败。搜索树深度至多为 $k$，节点数为 $O(2^k)$。若每个节点用 $O(1+n+m)$ 时间处理当前图，就得到

的 RAM 模型上界，进而符合编码长度下的 $f(k)N^{O(1)}$ 形式。[1][2]

这里真正缩小分支的是约束：不是从所有 $n$ 个顶点中任选一个，而是由一条未覆盖边把必要选择压缩到两个端点。三角形图也能直接检验规则：$k=1$ 时，无论选哪个端点，另两点之间仍有边；$k=2$ 时，选任意两点即可覆盖全部边。

参数选错，结论会完全不同 ​

对 SAT，以变量个数为参数时，枚举全部 $2^k$ 个赋值并检查公式，立即给出 FPT 算法。若改以每个子句最多含多少个文字为参数，固定到 $k=3$ 就包含 3-SAT；若这个参数化问题属于 FPT，则 3-SAT 会有多项式算法，从而推出 $P=NP$。

因此“SAT 是不是 FPT”缺少了必要信息；需要说明参数是什么。树宽、解大小和修改距离虽然都可能是小整数，却编码了不同结构，不能把对一个参数的算法保证移植给另一个参数。

最大独立集提供了结构参数的具体例子。若输入同时给出宽度 $k$、含 $q$ 个节点的 nice 树分解，逐袋动态规划理路树宽上的动态规划treewidth dynamic programming · DP on tree decompositions以最大独立集的完整逐袋计算，证明树分解边界状态、合并去重与回溯，并区分宽度、袋数和分解成本。只需对每袋的至多 $2^{k+1}$ 个选择子集计算最优值，表计算时间为 $2^k\mathrm{poly}(k)q$，另计图与袋的预处理。这里的参数是树宽，不是希望找到的独立集大小。$q$ 是输入分解的规模，也必须计入完整输入长度；若输入只有图，还需计寻找分解的参数化算法成本。把指数放在接口宽度上，才是这一 FPT 机制的实质。

有界搜索树和核化展示了两种基本路径。树宽上的动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。则利用窄接口限制状态数，颜色编码利用随机标记捕获小结构；它们能否给出 FPT，最终仍要回到 $f(k)N^c$ 检查。FPT 归约理路FPT 归约FPT reduction · Parameterized reduction在 f(k)N^{O(1)} 时间内保持答案，并把目标参数限制为原参数函数的参数化 many-one 归约。用于传递参数化可解性，W[1] 等层级理路W 层级与 W[1]W hierarchy以加权常深电路可满足性和大扇入门层数组织参数化困难性的 W 层级。用于组织条件困难性，这些都是围绕定义发展的工具，而不是定义之前必须掌握的前置概念。

核化：先把大图压到参数规模 ​

同一个问题还能展示核化理路核化Kernelization在总输入多项式时间内把参数化实例约化为大小只依赖参数的等价实例。的作用。设当前剩余预算为 $k$。若一个顶点的度大于 $k$，任何大小至多为 $k$ 的覆盖都必须选它；否则，为覆盖它的全部关联边，就得把它的所有邻居都选入，超过预算。

反复应用这条规则，每选一个被迫顶点就删除它及关联边，并把 $k$ 减一；同时删除孤立顶点。若预算耗尽而仍有边，则拒绝。规则结束后，图中最大度不超过剩余的 $k$。

此时，$k$ 个顶点最多覆盖 $k^2$ 条边。所以若剩余边数大于 $k^2$，立即判定无解；否则非孤立顶点至多为 $2k^2$ 个，得到一个大小仅依赖参数的等价实例。重新编号顶点后，还能使图的编码长度由 $k$ 的多项式控制，而不是保留原始的大编号。

这个核可以再交给分支算法。核化削减的是输入规模，搜索树控制的是组合选择；两种机制互补。还原实际解时，要把预处理阶段被迫选择的顶点加回去。

对通常的可判定参数化问题，FPT 与存在大小受某个可计算函数 $g(k)$ 控制的核等价。但一般核不必是多项式核：后者要求核大小为 $k^{O(1)}$，是额外而更强的结论。不能从“属于 FPT”直接推导“总能先压成参数的多项式规模”。[1]

这里的界是算法的时间复杂度理路时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。，必须同时说明输入长度和参数。