第29篇讨论输入长度与伪多项式，第30篇用近似比约束点覆盖的解质量。参数化算法采用另一条路线：仍求精确可行解，把指数成本限制在某个结构参数上。参数是否足够小，必须从问题输入中说明，不能只给变量改名。

本篇实现简单无向图的k顶点覆盖判定与解恢复。返回一个大小不超过k的覆盖，或明确表示不存在；不要求返回最小覆盖，也不以近似解替代预算判定。

n、k与编码长度

设图有n个顶点、m条边，预算k为非负整数，N是图和预算的输入编码长度。一个参数化问题属于FPT，要求存在f(k)N^c时间算法，其中常数c不依赖k，f只依赖k。参数可以影响前面的函数，却不能悄悄进入N的指数。

枚举至多k个顶点的所有子集，可以给出n^{O(k)}一类成本。固定k时它是多项式，但多项式次数随k变化，这是XP型上界。仅凭这个上界不能证明该算法是FPT，也不能证明问题不存在更好的FPT算法。

例如n从一千增至一万，n^k项增加10^k倍；2^k乘一个线性图扫描项，在同样稀疏度与固定k下只随图规模线性增长。这里只比较公式，不是本机跑分或任何规模下的实际速度承诺。

一条未覆盖边给出两个分支

沿用第30篇覆盖定义：每条边至少有一个端点在结果集合内。输入顶点为0到n−1，拒绝自环与重复无向边，包括以相反方向重复提供同一条边。这样边表表示的是简单无向图，不需要在度数或边数中处理多重计数。

如果没有剩余边，空集就是剩余问题的成功答案；如果还有边而预算为0，返回None。空集与None必须区分，否则空图成功会被错误判成失败。负k作为非法输入拒绝，即使图为空也不例外。

选一条剩余边(u,v)。任何覆盖必须包含u或v。第一分支选u，删除所有与u相接的边，预算减1；第二分支同样处理v。子问题若返回覆盖，就把选中的端点加入并返回。两个分支都失败才返回None。

每次挑选的端点来自尚未覆盖的边。先前已选顶点的所有关联边早已删除，所以同一路径不会反复选择同一顶点。返回的集合大小因而受预算扣减次数控制。

正确性不依赖搜索顺序

对剩余预算归纳。无边时空集覆盖全部剩余边；预算为0而有边时，不存在合法覆盖。对一般状态，任一可行覆盖必须含(u,v)的至少一个端点。

若含u，去掉u以后，其余点覆盖所有未被u覆盖的边，且使用至多k−1个点，所以第一子问题保留了这个解。含v时第二子问题同理。反过来，任一子问题的覆盖加上对应端点，都覆盖原图全部边并满足预算。

因此分支不会漏掉合法解，返回的解也必然合法。先尝试哪一端只影响返回哪一个覆盖和访问多少搜索节点，不影响存在性答案；第一个成功覆盖未必是全图最小覆盖。

指数来自预算深度

每层最多产生两个子节点，每条路径至多选择k个点。因此搜索树节点数至多2^{k+1}−1。若每节点扫描并复制边表，按常数大小编号与基本整数操作计费，每节点O(m+1)，总计O(2^k(m+1))。实现不遍历全部n个顶点，即使很多编号是孤立点，也不会为它们建立搜索状态。

递归沿一条路径保留若干边表，保守空间界O((k+1)(m+1))，不能把搜索树节点总数直接当作同时驻留空间。这里是确定性的最坏搜索界，既不是期望也不是高概率界；Python整数编号的比较与集合操作还受表示及容器成本影响。入口用set拒绝重复边，线性校验时间依赖期望常数访问假设；它与确定性的二叉分支节点上界分别计费，不把整个Python入口宣称为同一最坏时间保证。

输入以二进制n和边表表示时，n本身未必受N的多项式限制；上面的搜索界只依赖显式边数m。m与编号位宽受N约束，编号比较等代价可以放入与k无关的多项式因子，因此参数化形式仍是f(k)N^{O(1)}。Python递归实现还受解释器栈深限制，教学检查使用小k，不承诺在任意大k上完成运行。

核化把剩余实例限制在参数范围

简单图中，若一个顶点的度数大于剩余预算k’，任何大小至多k’的覆盖都必须选它。否则必须选它的全部不同邻居，数量超过预算。选定后删除其关联边并把预算减1，反复使用的是更新后的预算，不能一直用原始k。

当剩余最大度不超过k’，任取k’个点最多覆盖k’^2条边。因此剩余边数大于k’^2时可以拒绝；否则删除孤立点，至多还有2k’^2个非孤立顶点。被强制选择的点需另存，用于从剩余解恢复原解。

这一规则保留“预算内是否有解”的等价性，给出规模仅依赖参数的剩余实例。它是核化的一个例子，本文没有把这层预处理加入代码，也不把其更小规模界算进实际分支实现。

简单图前提不可丢。两个顶点之间重复列出多条平行边，k’=1时任取一个端点就能覆盖；若把重复边数当作不同邻居数，就会错误地把两个端点都判为必选。

折半枚举没有自动消除输入指数

Meet-in-the-Middle把n个选择对象分成两半，枚举两侧后匹配组合，可以在适当问题中把2^n级枚举改成约2^{n/2}级。它通常仍是关于n的指数算法，而且还要计入两侧记录存储与匹配成本。

这个界不能单独证明相对于另一个小参数k的FPT：固定k后，n仍可以无界增长，不能把2^{n/2}放进只依赖k的f(k)。若参数本来就选n，或先核化到大小至多g(k)再折半，结论会不同，必须重新写清参数。

所以判断应针对参数与算法界的组合。n^k上界、2^k乘多项式、2^{n/2}分别把成本放在不同位置，不是同一个“指数优化”的标签。

可复跑检查

接口vertex_cover(n,edges,k)返回集合或None。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_vertex_cover_fpt.py

本次退出码为0。枚举n=0到5的全部1100个简单图及6505个预算实例，其中4021个可行；另外检查100个固定种子随机实例、2个显式边界与6种非法输入。

独立参照枚举全部顶点子集，直接判断是否覆盖每条边，不沿用两端分支逻辑。对返回集合还单独检查编号范围、大小和覆盖性。原始结果见writing-plans/advanced-algorithms/evidence/vertex-cover-fpt-results.json。

这些有限检查验证返回语义，不证明2^k上界，也没有测量搜索节点数或速度交叉点。复杂度依据预算递减与分支树证明；核化与折半枚举只用于说明参数化方法的关系，不计为本次已运行实现。

练习

  1. 三角形在k=1与k=2时分别返回什么类型的结果？手画选择一条边两端的搜索树，指出为何空集不能代替None。
  2. 剩余预算k’=2、最大度不超过2时，5条边为什么可以拒绝？给出只有一条边的k’=1实例，解释为何“顶点数超过k’^2就拒绝”是错误规则。

参考资料