参数化问题

参数化问题不把所有输入都视为同样困难，而是把输入主体 $x$ 与结构尺度 $k$ 分开，隔离一个希望在实际中较小的量，如解大小、树宽或编辑次数，并问困难是否只集中在这个维度、代价能否主要由它承担。参数不是附加注释，而是问题定义的一部分；同一底层实例选择不同 $k$ 会形成复杂度完全不同的参数化问题。编码通常要求 $k$ 可从实例中读取或显式给出，并以总输入长度分析多项式部分。

参数化顶点覆盖询问是否存在大小至多 $k$ 的覆盖。以解大小为参数时，可设计每次都让 $k$ 下降的分支算法和核化；若改以树宽为参数，典型路线则是树分解动态规划。两者共享同一底层判定问题，却把困难集中到不同结构尺度。暴力枚举 $n^k$ 虽对每个固定 $k$ 都是多项式，却不具有 $f(k)n^{O(1)}$ 的 FPT 形式。

SAT 以变量数为参数时可在 $2^k\mathrm{poly}(n)$ 时间穷举，以子句宽度为参数却不会自动得到同样结论。把 $k=n$ 机械附加到任意问题总能形成合法参数化，却通常没有算法价值；反过来，真实数据中 $k$ 较小只是经验假设，不是 FPT 证明。参数化归约还必须把新参数控制为原参数的函数，否则困难可能被悄悄塞进参数增长。

参数化问题建立在语言公理库形式语言Formal language · Language over an alphabet固定字母表上有限字的任意集合，是识别器、文法与判定问题共同描述的对象。与参数公理库自然数模型Natural numbers · Peano system由零元、后继和二阶归纳原则范畴性刻画的离散数系模型。的二元结构上。FPT公理库参数化复杂度类 FPTFixed-parameter tractable · FPT可在 f(k)n^O(1) 时间内求解的参数化问题类。固定 $f(k)n^{O(1)}$ 的可处理性基线，FPT 归约公理库FPT 归约FPT reduction · Parameterized reduction在 f(k)|x|^{O(1)} 时间内保持答案，并把目标参数限制为原参数函数的参数化 many-one 归约。控制目标参数增长，核化公理库核化Kernelization · Problem kernel在总输入多项式时间内把参数化实例约化为大小只依赖参数的等价实例。研究多项式预处理后的实例大小，W 层级公理库W 层级与 W[1]W hierarchy · W[1]以加权常深电路可满足性和大扇入门层数组织参数化困难性的 W 层级。组织条件困难性。这些页面分别承担类、归约、预处理和困难度；对象页不把它们压成一段混合定义。

算法设计中，有界搜索树公理库有界搜索树Bounded search tree对局部障碍作完备分支，并让参数预算在每条分支严格下降。直接控制每个分支对参数的下降，迭代压缩公理库迭代压缩iterative compression逐步扩大实例，并把已有 k+1 解压缩为 k 解的参数化算法范式。把大小 $k+1$ 的解逐步压回 $k$，Color Coding公理库Color Codingcolor-coding · 颜色编码法随机把顶点染成 k 色，将简单子图的顶点互异约束转成颜色子集动态规划。用随机着色暴露小子结构，树宽动态规划公理库树宽上的动态规划treewidth dynamic programming · DP on tree decompositions在 nice tree decomposition 的小 bag 边界上记录状态，以 f(k)n 时间求解近树图问题。则把全局问题限制在小分隔袋上。每条路线都必须写明参数是什么；把 $2^k{n}^{O(1)}$ 中的 $k$ 换成输入规模 $n$，就不再是 FPT 结论。