有界搜索树

分支递推 ​

对参数化问题公理库参数化问题Parameterized problem实例与非负整数参数共同组成的判定问题。发现尚未满足的局部障碍后，列出覆盖所有可行解的有限选择。若各分支让 measure 分别减少 (d_i>0)， [ T(k)\le\sum_iT(k-d_i)+\operatorname{poly}(n). ] 每条根叶路径的预算严格下降，搜索深度受 (k) 控制；branching vector ((d_1,\ldots,d_r)) 决定树的指数底。

Vertex Cover 遇到未覆盖边 (uv)，任何覆盖必含 (u) 或 (v)。算法必须分别选择两端、删除相应关联边并令 (k\leftarrow k-1)；正确性来自两个分支覆盖全部解，而不是“高度数端点通常更好”。

一棵搜索树的状态 ​

实例有边 ((a,b),(b,c))，预算 (k=1)。在边 ((a,b)) 上分支：选择 a 后还剩 ((b,c))，预算已为 0，故失败；选择 b 会删除两条关联边，图为空，恢复解 ({b})。

预算为负时失败，无障碍时成功。每个递归帧还要保存本分支加入的顶点和图修改，返回时 rollback；若两个分支共享可变图却没有隔离状态，一个分支的删边会污染另一个分支。

安全约简 ​

孤立顶点不覆盖任何边，可以直接删除而不消耗预算。若顶点 (v) 的唯一邻居是 (u)，则存在一个最优覆盖包含 (u)：任何只选 (v) 的覆盖都可用 (u) 替换，且 (u) 还可能覆盖更多边。因此可安全选择 (u)、删除其关联边并把预算减一。

约简规则必须同时保持可解性与剩余预算的对应关系。Kernelization 可在搜索前把实例缩到参数函数大小，也可在节点内应用，但它有自己的等价性证明，不是有界搜索树定义的一部分。

Branching vector 推导 ​

普通 Vertex Cover 两分支各下降 1， [ T(k)\le2T(k-1)+\operatorname{poly}(n), ] 所以节点数为 (O(2^k))。若额外规则让两个分支分别下降 1 与 2，设齐次解形如 (x^k)，便有 (x^2=x+1)，指数底为黄金比 (\varphi<2)。

Measure-and-conquer 可给不同对象非整数权重，使真实进展比整数参数更细。但每条规则都要证明 measure 严格下降、初始 measure 受参数控制，并与成功/失败基例相容；改变记账符号本身不会让算法更快。

时间与适用边界 ​

深度至多初始 (k) 不代表节点数为 (O(k))；二叉树可有 (2^k) 个叶。每节点若复制整图需要 (O(n+m))，总时间还要乘该多项式因子；持久化或修改栈能降低常数，但须保持分支隔离。

若某分支不降低 measure，递推可能按 (n) 指数增长甚至不终止。启发式只探索看似更好的一个端点也会漏解。有界搜索树把指数隔离在参数 (k)，得到 (f(k)\operatorname{poly}(n)) 的 FPT 形式；仅在实验里观察到 (k) 小不构成这项证明。

普通 backtracking 的指数常按输入规模 (n)；bounded search tree 必须展示参数下降和完整分支覆盖。两者代码都可能写成递归 DFS，复杂度来源却不同。

参考资料

• Downey, Fellows, Parameterized Complexity, 1999.
• Cygan et al., Parameterized Algorithms, 2015.
• Niedermeier, Invitation to Fixed-Parameter Algorithms, 2006.