树宽上的动态规划

边界状态原则 ​

给宽度 $k$ 的树分解公理库树分解与树宽Tree decomposition · Treewidth用按树组织的顶点袋覆盖图，并以最小最大袋大小衡量图偏离树结构的程度。，每个 bag 至多 $k+1$ 个原图顶点。处理某分解节点的子树时，已处理图与未处理图只能通过当前 bag 交互；DP 状态只需记录 bag 顶点的选择、颜色、连通关系等边界信息，而非整个已处理子图。

Nice decomposition 转移 ​

leaf 给空状态；introduce vertex 加入一个 bag 顶点并枚举其局部状态；introduce edge 检查/更新边约束；forget vertex 在它离开边界前汇总所有可能；join 的两个孩子有同一 bag，要组合彼此内部独立但边界一致的状态。join 最容易重复计算 bag 顶点的权重，需只在固定引入/遗忘时计一次。

独立集例子 ​

状态是 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 会接受在未来永远无法连接的部分解。

参考资料

• Hans Bodlaender, Treewidth: Algorithmic Techniques and Results, MFCS, 1997.
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015.