参数化问题

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

参数化顶点覆盖询问是否存在大小至多 $k$ 的覆盖。以解大小为参数时，任选尚未覆盖的边 $uv$，任何解必选 $u$ 或 $v$，所以分成两支，分别删掉所选端点及其关联边，并把预算减一。没有边时接受，预算耗尽却仍有边时拒绝。搜索树至多有 $2^k$ 个叶，每个节点只做多项式工作，得到 $2^k{n}^{O(1)}$ 界；核化还可在搜索前缩减实例。若改以树宽为参数，典型路线则是树分解动态规划。两者共享同一底层判定问题，却把困难集中到不同结构尺度。暴力枚举 $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^c 时间求解的参数化问题类；用顶点覆盖分支与核化解释固定指数及参数选择。固定 $f(k)n^{O(1)}$ 的可处理性基线，FPT 归约理路FPT 归约FPT reduction · Parameterized reduction在 f(k)N^{O(1)} 时间内保持答案，并把目标参数限制为原参数函数的参数化 many-one 归约。控制目标参数增长，核化理路核化Kernelization在总输入多项式时间内把参数化实例约化为大小只依赖参数的等价实例。研究多项式预处理后的实例大小，W 层级理路W 层级与 W[1]W hierarchy以加权常深电路可满足性和大扇入门层数组织参数化困难性的 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以最大独立集的完整逐袋计算，证明树分解边界状态、合并去重与回溯，并区分宽度、袋数和分解成本。则把全局问题限制在小分隔袋上。每条路线都必须写明参数是什么；若只写成 $2^n$，就丢失了“小参数、大输入”时的收益；但若所选参数本来就是 $k=n$，$2^k{n}^{O(1)}$ 仍形式上是 FPT，只是这个参数化几乎没有隔离困难。