有界搜索树

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

一棵搜索树的状态 ​

实例有边 $(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，

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

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

分支向量给出参数递推 T(k)≤Σi T(k−di)+poly(n)，递归树法公理库递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。把每条根叶路径的参数下降和每层分支数转成 O*(ck) 界。只报告最大分支数而忽略各分支下降量会得到过松甚至错误的底数。

时间与适用边界 ​

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

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

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