有界搜索树

搜索树的每条边都代表一种结构性选择，不同分支可以覆盖部分相同的解，参数则像沿根到叶不断消耗的预算。判定或见证搜索的正确性要求有解时至少一个分支仍有解，复杂度要求每个分支都让同一套测度下降；只满足其中一项，要么漏解，要么仍可能展开成由输入规模控制的指数树。

一棵搜索树的状态 ​

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

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

安全约简 ​

孤立顶点不覆盖任何边，可以直接删除而不消耗预算。若顶点 $v$ 的唯一邻居是 $u$，则存在一个最优覆盖包含 $u$：任何只选 $v$ 的覆盖都可用 $u$ 替换，且 $u$ 还可能覆盖更多边。因此可安全选择 $u$、删除其关联边并把预算减一。这个规则保持大小至多 $k$ 的覆盖是否存在，并能恢复一个解；它不枚举所有覆盖。例如仅有边 $uv$ 时，选择 $u$ 会省略另一个最优覆盖 $\{v\}$。

约简规则必须同时保持可解性与剩余预算的对应关系。Kernelization 可在搜索前把实例缩到参数函数大小，也可在节点内应用，其等价性保证缩小后的实例仍回答原来的可解性问题。

Branching vector 推导 ​

普通 Vertex Cover 两分支各下降 1，

所以节点数为 $O(2^k)$。若额外规则让两个分支分别下降 1 与 2，设齐次解形如 $x^k$，便有 $x^2=x+1$，指数底为黄金比 $\phi <2$。

Measure-and-conquer 可给不同对象非整数权重，使真实进展比整数参数更细。但每条规则都要证明 measure 严格下降、初始 measure 受参数控制，并与成功/失败基例相容；较紧的下降量据此给出更准确的搜索树规模界。

递归树法理路递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。把分支向量转成运行时间界。若每节点的处理成本为多项式，且分支向量至少含两个分支，齐次方程 $\sum _i{c}^{-d_i}=1$ 的根 $c>1$ 给出指数因子 $c^k$，常记作 $O^{\ast }(c^k)$，其中星号省略多项式因子。

时间与适用边界 ​

在每次至少消耗一个单位预算的二分支搜索中，深度至多为初始 $k$，叶子数却可达 $2^k$。每节点若复制整图需要 $O(n+m)$，总时间还要乘该多项式因子；持久化或修改栈能降低常数，但须保持分支隔离。

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