树宽上的动态规划

树分解的 bag 是已处理子图与未来部分之间唯一可见的边界。只要状态保存所有可能影响未来扩展的信息，内部细节便可被一个最优值摘要替代；宽度 $k$ 控制边界大小，也就把指数限制在 $f(k)$ 而非整张图的顶点数上。

独立集例子 ​

状态是 bag 的独立子集 $S$，值为已处理部分中与 $S$ 相交恰为 $S$ 的最大独立集大小。Introduce 检查新顶点与 $S$ 内邻居，forget 在“选/不选”中取最大，join 合并两值再减去被两边都计入的 $|S|$。状态数 $2^{k+1}$，给定分解后时间 $O(2^k\mathrm{poly}(k)n)$。

边界 ​

分解树节点不是原图顶点。Hamilton cycle 等连通问题若直接记录 bag 的分区，状态可达 Bell 数；需 rank-based、Cut&Count 或代表集进一步压缩。算法输入若不含分解，还必须计求 tree decomposition 的 FPT/近似成本。$f(k)n$ 只在参数 $k$ 小时有意义。

状态充分性的证明 ​

正确性通常按分解树归纳：两份已处理部分若在当前 bag 上具有相同状态，则对任何未处理上方图，它们可扩展为解的可能性和最佳代价相同。这个“可替换性”证明比列出转移更重要；若状态漏掉边界连通关系，join 后可能把两条路径错误拼成环。

Nice decomposition 可由普通分解在 $O(kn)$ 大小内转换，宽度不增加常数以上。转化成本和 bag 内转移的 $\mathrm{poly}(k)$ 因子应计进 $f(k)n$。

独立集状态的完整转移 ​

对每个 bag $B_t$ 和子集 $S\subseteq B_t$，令 $D{P}_t[S]$ 为已处理子图中、与 bag 交恰为 $S$ 的最大独立集大小；若 $S$ 内含原图边则状态无效。Nice decomposition 上的状态变化为：

1. introduce $v$：选择 $v$ 时检查它与 $S\setminus \{v\}$ 无边；
2. forget $v$：在子状态含或不含 $v$ 两者中取最大；
3. join：两孩子取同一 $S$，相加后减去 bag 中被重复计算的 $|S|$；
4. leaf：从空 bag 的零值开始。

每个 bag 有 $2^{k+1}$ 个子集，若转移每状态只做 $\mathrm{poly}(k)$ 工作，总时间 $2^{O(k)}n$，前提是已给出含 $O(n)$ 个节点的 nice decomposition。求最优树分解本身不是免费的，若输入只给图，就要把分解算法成本另计。

连通性问题的状态不只记录选中顶点，还要记录 bag 上的连通分区，状态数可能是 $k^{O(k)}$。若忘掉某顶点时没有记录其分量是否已封闭，DP 会接受在未来永远无法连接的部分解。