参数化复杂度

破除误解：加一个参数不是给 NP 完全问题开后门#

常见的读法是：NP 完全「在理论上无解」，所以要「限制输入」。参数化不是随便限制。它要求你指明哪一个整数承载难度，并且算法的多项式部分必须对 $n$ 均匀成立。

形式定义：语言 $L$ 是固定参数可轨（FPT, fixed-parameter tractable），当存在可计算函数 $f$ 和常数 $c$，使得输入 $(x,k)$ 能在 $f(k)\cdot |x|^c$ 时间内判定。

$f$ 可以是 $2^k$、$k!$ 甚至 $2^{2^k}$，多项式的指数 $c$ 却不许跟着 $k$ 走。

对照：XP 类允许 $n^{g(k)}$。团问题的枚举是 $n^{O(k)}$，落在 XP，长期不相信它在 FPT 里。

2000 年代之后，W 层次把「像团这样的问题」安放在 FPT 之上，避免一句「都是指数」把能用的算法和不能用的算法混在一起。

另一个误解是把参数化当成近似算法的别名。近似谈的是目标值离最优有多远；参数化谈的是精确解能否把指数隔离到参数上。

两者经常联用——核化给出的小实例可以再喂给近似或 SAT 求解器——但问题本身不是同一类。

现场：顶点覆盖如何变成 FPT#

最简单的有界搜索树已经够用。若一条边的两端都未被覆盖，必须挑其中一个顶点进入覆盖。对每条未覆盖边分支一次，深度至多 $k$，得到 $2^k$ 个叶子；每个叶子上检查剩余图是否已空。

总时间 $O(2^k n)$。核化更狠。Buss 规则说：度数大于 $k$ 的顶点必须进覆盖，否则它的邻接边无法被 $k$ 个顶点打完；于是图里剩下的顶点度数 $\le k$，且边数若超过 $k^2$ 则可直接拒绝。

输出的等价实例大小只依赖 $k$。陈建尔、Iyad Kanj、Ge Xia 等人把顶点覆盖的核做到线性规模；Nemhauser–Trotter 的 LP 半整性给出另一条 $2k$ 顶点的核。

FPT 不只是「指数更好看」。核化把预处理变成定理：存在多项式算法，把实例压到 $g(k)$ 大小，当且仅当问题在 FPT 中（在标准技术假设下）。

工程上，这就是编译器里「先砍实例再调用求解器」那一层的正确性证明。树宽把另一类图问题拖进 FPT。

若图的树分解宽度为 $w$，Courcelle 定理说：任何可用一元二阶逻辑（MSO）写下的图性质，都能在 $f(w)\cdot n$ 时间内判定。哈密顿回路在一般图上 NP 完全，在树宽有界的图上却是线性时间——函数 $f$ 往往是天文数字，但指数已经不在 $n$ 上。

动态规划在袋子上做状态压缩，是算法教材里「树上 DP」的一般化。

核心：W 层次、核化下界与 ETH#

FPT 之外需要一张难度地图。唐尼、费洛斯与合作者用加权电路可满足定义 W[1]、W[2]、……。直觉：W[1] 对应「存在 $k$ 个输入使深度有界的 weft-1 电路输出 1」。

$k$-团是 W[1] 完全的；$k$-集合覆盖是 W[2] 完全的。

若 FPT = W[1]，一批被认为必须 $n^{\Theta(k)}$ 的问题会突然拥有 $f(k)n^{O(1)}$ 算法，后果类似 P = NP，只是爆炸发生在参数轴上。多数人相信 FPT $\neq$ W[1]，证明同样未完成。

核化也有下界。Fortnow 与 Santhanam、Bodlaender 等人用或组合（OR-composition）证明：若某个 NP 完全问题有多项式核，则多项式层次会塌缩。因此「先压成 $k^{100}$ 再暴力」并不总被允许。

顶点覆盖幸运地有多项式核，团问题在标准假设下没有。指数时间假设（ETH, Impagliazzo–Paturi）给出更细的数字。ETH 说：3-SAT 没有 $2^{o(n)}$ 算法。

由此可推出：许多 FPT 算法的 $2^{\Theta(k)}$ 不能再降到 $2^{o(k)}$，否则会撞上 ETH。

细粒度复杂度把这条线延伸到 SETH 和 3SUM，见 细粒度复杂度；参数化这边先把 ETH 当作「指数常数也有下界」的工具。

颜色编码（Alon、Yuster、Zwick，1995）是 FPT 工具箱里最像魔术的一件。要找长度为 $k$ 的路径，随机给顶点涂 $k$ 种颜色，再只在彩色路径上做 DP，期望时间 $2^{O(k)}n$。

它把组合对象编码成颜色碰撞，而不是枚举 $n^k$ 个顶点子集。

机制：搜索树、冠归约与迭代压缩#

顶点覆盖的 $2^k$ 只是起点。分支向量把底数往下压：度数 1 的顶点没有选择，必须收它的邻居；度数 3 以上的顶点触发不对称分支。

陈建尔、Kanj、Xia 把判定版顶点覆盖推到大约 $1.2738^k n^{O(1)}$。分析是线性递推，不是口号：若一次分支拆成「删 1 个」和「删 2 个」两条臂，特征根决定底数。

工程上，搜索树必须和核化交替。每层先跑 Buss 规则和高度数折叠，再分支，否则稠密局部会把 $2^k$ 的常数放大成不可用。

生物网络里 $k=30$ 的覆盖在 2010 年代已经能在单机上解；同一套代码对 $k=80$ 仍然爆炸。迭代压缩是另一件标准零件。

假设手里已经有一个大小为 $k+1$ 的可行解，问能否压到 $k$。把这 $k+1$ 个顶点暂时拿出图，剩余必须已经满足性质——于是候选只藏在这 $k+1$ 个点的子集里。

子集是 $2^{k+1}$，对每个子集检查补集是否可解。许多「删 $k$ 个顶点使图变成某性质」的问题走这条路，包括早期的簇图编辑。

Reed、Smith、Vetta 用它处理反馈顶点集；Niedermeier 的教材把它写成可复用模板。Crown 归约说明核化不必只靠度数阈值。若独立集 $I$ 与其邻居 $H$ 形成冠，且霍尔婚配条件成立，则 $H$ 可以强制进覆盖，$I$ 可以删掉。

匹配理论在这里是预处理规则，不是事后优化。Nemhauser–Trotter 的 LP 松弛把顶点分成三段：必须进最优解、必须不进、两边都可。

半整性保证丢掉前两段后，留下至多 $2k$ 个顶点。这是组合优化把核化写成线性规划的例子。寄存器分配里的干扰图常常接近弦图；顶点覆盖和着色在弦图上多项式，但编译器仍会先用覆盖数当参数，把剩余冲突图压进 ILP。

这里 FPT 不是替代求解器，是给求解器喂合法的小核。

机制：W[1] 完备性在数哪一层量化#

团的 W[1] 完备性是参数化难度的原点。fpt-归约允许 $f(k)\cdot n^c$ 时间，并且新参数 $k'$ 只许是旧参数的函数。若允许 $k'=n$，归约就塌成普通多项式归约，W 层次会失去意义。

从加权电路 SAT 打到 $k$-团，构造必须把「weft-1 电路的 $k$ 个输入」编码成「图上 $k$ 个顶点」，而不能把电路规模写进新参数。

weft 是输入到输出路径上大扇入与门的最大数目。W[1] 对应「一层大与门」，形状像「存在一个大小为 $k$ 的集合使局部约束同时满足」。

$k$-团正是这种形状：存在 $k$ 个顶点，它们两两相邻。

W[2] 多一层，对应支配集和集合覆盖：存在 $k$ 个集合，覆盖全部元素——量化交替更深。Flum 与 Grohe 把 weft 定义写进电路深度和大门位置；教材若省略电路，只说「团难、覆盖更难」，会把层次读成口味。

颜色编码给的是上界，不是层次坍塌。

$k$-路径因此在 FPT 里，尽管朴素枚举是 $n^k$。

Alon–Yuster–Zwick 的随机着色成功概率是 $k!/k^k \approx e^{-k}$，重复 $e^{k}$ 次多项式次即可把失败压下去。决定性版本用完美哈希族，空间随 $k$ 指数涨，多项式部分仍只依赖 $n$。

这恰好示范 FPT 的定义：指数可以很难看，只要不乘进 $n$ 的指数。多维匹配、$k$-和、Steiner 树在部分参数下也走颜色编码或代表性集。

Fomin、Lokshtanov、Saurabh 等人的代表性集把「保留一个可扩展子集」做成线性代数选取，底数常落到 $2^{O(k)}$。这些算法改变的是上界地图，不改变 W[1] 对团的判决。

机制：或组合、核大小与 ETH 钉死的底数#

Fortnow–Santhanam 的或组合说：若你能把 $t$ 个实例压成一个小核，使得核为 yes 当且仅当至少一个实例为 yes，则多项式层次会塌。

Bodlaender、Downey、Fellows、Gutin 把这套技术应用到一批 NP 完全问题。团没有多项式核（在标准假设下），即使它在 XP 里显然可解。「先压再暴力」对团是禁止的；对顶点覆盖是允许的。

Dell 与 van Melkebeek 后来把某些问题的核下界钉到 $k^{2-\varepsilon}$：即使有核，也不能任意小，否则同样塌缩。ETH 给出另一类数字。Impagliazzo–Paturi 假定 3-SAT 没有 $2^{o(n)}$ 算法。

把 3-SAT 近似线性地归约到 $k$-顶点覆盖，就得到：顶点覆盖没有 $2^{o(k)}\mathrm{poly}(n)$ 算法。于是 $1.28^k$ 仍可能，$2^{\sqrt{k}}$ 那种亚指数在 ETH 下被禁止。

$k$-团更狠：ETH 意味着没有 $f(k)\,n^{o(k)}$ 算法，$n^{k/\log k}$ 也不行。

这解释了为什么团停留在 XP：不是没人肯找 FPT 算法，是假设禁止。SETH 把同样逻辑推到底数 $2$ 的系数，那是细粒度的领地。

参数化这边先把 ETH 当作「单指数已经接近天花板」的尺子。Cygan、Nederlof、Pilipczuk 等人的 Cut & Count 把若干连通性问题做到 $2^{O(k)}n^{O(1)}$，底数常是 $4$ 或 $2$，正好卡在 ETH 允许的形状里。

树宽 DP 的状态 $2^{O(w)}$ 也是同一形状：指数在宽度上，$n$ 只是线性扫描袋子。Courcelle 的非初等函数在这里被具体问题的单指数 DP 替换。

定理仍成立；编译器选的是能跑的常数，不是逻辑句子的一般性。生物信息学里的序列与网络问题曾是 FPT 的早期试验场。

Steiner 树、近亲集、以及若干缺失值填补，参数常常是「要解释的异常条数」而不是顶点数。

$k=12$ 的搜索树能跑；$k=40$ 仍要靠核化把实例先砍到几百个顶点，再交给 ILP。

这里论文里的 $1.28^k$ 很少被原样实现，实现的是 Buss 规则、LP 核与现成求解器的管道。

工程现场：底数表、背包与求解器分工#

把 $k=10$、$20$、$30$ 写进时间表，比再背一遍定义有用。$1.28^{10}$ 约为 $12$；$1.28^{20}$ 约为 $140$；$1.28^{30}$ 已经接近 $1600$。再乘上 $n=10^6$ 的多项式扫描，前两档是交互式可用，第三档开始要靠核化把 $n$ 先砍掉。

$2^{k}$ 的同一张表难看得多：$2^{30}$ 已经是十亿量级分支，缓存不友好。底数从 $2$ 降到 $1.3$，等于把可处理的 $k$ 往外推了大约一倍。

背包问题 提供对照。经典伪多项式 $O(nW)$ 已经是参数化思维：容量 $W$ 是参数，只是多项式写在 $W$ 上，而不是 $f(W)n^{O(1)}$ 的 FPT 形态。

若把利润上界或最优值当参数，存在更接近 FPT 的路线；若把物品种数当参数，维度爆炸会立刻送回 XP。同一背包，参数不同，算法不是同一件。

图遍历 的 BFS 给出最短路，本身是多项式；一旦加上「必须经过 $k$ 种颜色的路径」，颜色编码才进场。FPT 经常不是替换多项式算法，而是给多项式算法加一层组合约束后的急救包。

与整数线性规划和 SAT 求解器 可以串起来：先跑 Nemhauser–Trotter 把实例压到 $2k$ 顶点，再把核交给 MIP 或 CDCL。

这正是「核化是定理」在流水线里的位置。fpt-归约本身也可能把实例吹大：若输出图有 $k^{4}n$ 条边，后面的 $2^{k}n$ 在纸上仍是 FPT，在内存里已经先爆。

因此论文现在会同时报告归约膨胀、核的顶点数、以及搜索树底数。少报任何一项，工程师都会把「FPT」读成不可用。

W[1] 完备性对建模也是警告牌。把「选 $k$ 个基因使它们两两相关」写成团，就不要指望单指数算法；改写成「删 $k$ 条边变成二部图」则可能立刻有核。同一张网络，问法决定复杂度类。

代价与争议#

FPT 的函数 $f$ 可以大到无法运行。Courcelle 定理的依赖是逻辑公式长度的非初等函数；「线性时间」在定理里成立，在编译器里常常不如针对具体问题手写的 $2^{O(w)}n$ DP。

参数化社区因此同时追两件事：存在性，以及单指数、$2^{O(k)}$、甚至 $1.28^k$ 这种工程常数。参数选错，理论就空转。把 $k$ 设成「边数」通常没有信息——边数已经和 $n$ 同阶。

有用的参数是解大小、树宽、顶点覆盖数、亏格、删除到森林的边数。选择参数本身是建模，不是免费午餐。

W 层次的完备性证明依赖 fpt-归约，细节比卡普归约更碎，教材里容易变成符号墙。对工程师更友好的接口其实是核化与搜索树：你不必先接受 W[1]，也能把顶点覆盖求解器做进生物网络或编译器寄存器分配。

还有一条与 SAT 求解器的竞争。现代 CDCL 求解器在工业实例上经常打赢最精致的 FPT 实现，因为实例有结构，而最坏情况 $f(k)$ 假定没有结构。

参数化理论解释的是最坏情况的指数隔离；它不保证每一个生物数据集都比 MiniSat 更快。两者应看成预处理与求解器的分工，而不是谁取代谁。

ILP 求解器（Gurobi、SCIP）在稀疏覆盖问题上也常赢过手写搜索树。FPT 论文报告的是最坏情况底数；工业对比必须把核化时间、缓存局部性和分支定界的下界剪枝算进去，否则数字不可比。

树宽求解器（如 libtw、或把袋子 DP 写进具体问题）在 $w\le 20$ 的社交或电路图上有用，在 $w=40$ 时 $2^w$ 状态已经上亿。「有界树宽」因此不是开关，是一条以 2 为底的账单。

跨域连接#

• 图论：树宽、路径宽、亏格先是结构图论里「这张图离树木有多远」的尺度，不是为算法临时发明的装饰参数。参数化把这些尺度写成动态规划的袋子宽度；Courcelle 定理能成立，是因为 MSO 句子的模型检验在树上可自动机化，再沿着树分解提升。Robertson 与 Seymour 的 minors 项目把「排除一个平面 minor」写成有界树宽。算法作者借用的是宽度数字：袋子 $w=20$ 与 $w=40$ 的 $2^w$ 差一百万倍，「有界」在定理里成立，在求解器里仍要先问宽度是几。
• 组合学：颜色编码把「存在一个 $k$ 元结构」改写成「随机着色后该结构变成彩色」。这是概率方法进算法的典型路径：期望给出 $2^{O(k)}$，再 derandomize 成哈希族。代表性集则把「保留可扩展子集」做成二项式系数上的线性无关选取。参数化并不回避随机，它只要求失败概率仍然只是 $k$ 的函数，从而多项式部分对 $n$ 均匀成立。
• 证明：核化下界用的是或组合与多项式层次，不是「我试过了没有小核」。这和 NP 完全性一样，是用归约把「小核存在」映射成「层次塌缩」。Dell–van Melkebeek 把核的大小本身做成可证伪的指数。于是预处理的极限也需要证明：工程上「先压缩再暴力」是否合法，取决于你面对的是顶点覆盖还是团，而不能只拿实现跑分。
• 概率：随机化 FPT 依赖集中不等式。颜色编码、随机分离、截止法都在 $k$ 维空间里做抽样。失败概率可以重复放大到 $n^{-\Omega(1)}$，多项式部分仍保持。这里随机不是启发式，是复杂度类里的正式资源：算法可以抛硬币，但硬币次数和失败率都必须写成 $k$ 的函数，而不能偷偷依赖输入分布。

参考文献#

• Downey, R. G. & Fellows, M. R. Parameterized Complexity. Springer, 1999.
• Downey, R. G. & Fellows, M. R. Fundamentals of Parameterized Complexity. Springer, 2013.
• Cygan, M. et al. Parameterized Algorithms. Springer, 2015.
• Alon, N., Yuster, R. & Zwick, U. "Color-Coding." Journal of the ACM 42(4):844–856, 1995.
• Impagliazzo, R. & Paturi, R. "On the Complexity of $k$-SAT." Journal of Computer and System Sciences 62(2):367–375, 2001.
• Bodlaender, H. L. et al. "On Problems without Polynomial Kernels." Journal of Computer and System Sciences 75(8):423–434, 2009.
• Courcelle, B. "The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs." Information and Computation 85(1):12–75, 1990.
• Chen, J., Kanj, I. A. & Xia, G. "Improved Upper Bounds for Vertex Cover." Theoretical Computer Science 411(40–42):3736–3756, 2010.
• Dell, H. & van Melkebeek, D. "Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses." Journal of the ACM 61(4):23, 2014.

延伸阅读#

• Niedermeier, R. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
• Flum, J. & Grohe, M. Parameterized Complexity Theory. Springer, 2006.