树宽上的动态规划 | Codeboy's Blog

树分解把一张图组织成许多局部区域。处理完某一支之后，该支内部与尚未处理部分的接触只能经过当前袋。因此，动态规划不必保存这一支所有解的完整顶点集合，只需按接口上的行为分类，再为每类保存最优值。

这里用最大独立集把这个原则落实为可执行的算法：给定有限非空简单无向图 $G=(V,E)$ 及其树分解，求一个尽量大的顶点集合，使集合内部没有边。目标不仅是得到最优数值，还要从表中找回具体顶点。以下所有值都把当前袋中已选顶点计入，因此两支合并时必须去重。

形式陈述

状态的精确定义

将分解树选根。记 $T_t$ 为节点 $t$ 的后代子树（包含 $t$ ）， $V_t=\bigcup_{x\in T_t}B_x$ ，并取诱导子图 $G_t=G[V_t]$ 。对每个 $S\subseteq B_t$ ，定义

F_t(S)=\max\{\,|I|:I\subseteq V_t,\ I\text{ 在 }G_t\text{ 中独立},\ I\cap B_t=S\,\}.

不可行时取 $-\infty$ 。特别地，只要 $S$ 本身包含一条原图边，这个状态便不可行。交集必须恰好等于 $S$ ：它同时指定哪些袋顶点已选、哪些未选。仅要求“包含 $S$ ”会把不同的接口选择混在一起，左右两支就可能无法协调。

四类节点与正确性

采用空叶、空根的 nice tree decomposition。每个内部节点只有以下三种形式：引入一个顶点、遗忘一个顶点，或合并两个与自己袋相同的孩子。节点名称描述它相对孩子的变化，计算方向始终是从孩子到父亲。本页把 $G_t$ 定义为诱导子图，所有原图边都已经包含在约束中，无须额外的“引入边”节点。一个原图顶点可能在不同分支各被引入一次。

空叶与引入

空叶只有 $F_t(\varnothing)=0$ 。若 $t$ 有一个孩子 $c$ ，且 $B_t=B_c\cup\{v\}$ ，称为引入 $v$ 。对独立的 $S\subseteq B_t$ ，

F_t(S)= \begin{cases} F_c(S),&v\notin S,\\ F_c(S\setminus\{v\})+1,&v\in S. \end{cases}

第二种情况要求 $v$ 与 $S\setminus\{v\}$ 无边，这已包含在 $S$ 独立的检查中。为什么不需要检查此前遗忘的顶点？首先 $v$ 不在孩子的任何后代袋中，否则运行交性质会迫使孩子袋也包含 $v$ 。其次 $v$ 不可能邻接 $V_c\setminus B_c$ 中的顶点：那个内部顶点的所有出现位置都在孩子子树内，而 $v$ 从不在那里出现，任何袋都无法覆盖这条假想边。因此加入 $v$ 时只检查袋内邻居即可。

任意父状态解删去 $v$ 后都是对应孩子状态解，给出公式的上界；反过来，每个孩子最优解按条件加入或不加入 $v$ 都可行，给出下界。两向论证合起来才得到等号。

遗忘

若 $B_t=B_c\setminus\{v\}$ ，则

F_t(S)=\max\bigl\{F_c(S),F_c(S\cup\{v\})\bigr\}.

这里 $V_t=V_c$ ，遗忘只是让 $v$ 离开接口，没有把它从已处理图或目标值中删除。父状态的每个解要么不选 $v$ 、要么选 $v$ ，恰好落入两个孩子状态之一；两个孩子状态的解又都满足父状态，所以取最大既无遗漏，也不引入非法解。

合并

若 $t$ 的两个孩子 $l,r$ 满足 $B_t=B_l=B_r$ ，则对可行状态

F_t(S)=F_l(S)+F_r(S)-|S|.

运行交性质给出 $V_l\cap V_r=B_t$ ；边覆盖再保证两个内部 $V_l\setminus B_t$ 与 $V_r\setminus B_t$ 之间没有边。于是，左右各取一个边界恰为 $S$ 的独立集，它们的并仍独立，而交恰为 $S$ ，所以大小是两值相加再减去 $|S|$ 。反过来，父节点任意独立集限制到两支后得到同一边界状态，其大小也遵守这一容斥式。因此孩子最优值既能构成父解，又给所有父解提供上界。

若任一孩子状态不可行，父状态也不可行；实现时直接跳过，不应把代表 $-\infty$ 的有限整数哨兵当成普通分数。上述论证按分解树归纳，证明所有表项都符合定义。空根 $z$ 满足 $V_z=V$ ，最终答案就是 $F_z(\varnothing)=\alpha(G)$ 。

直觉

状态为什么足够？分解的分隔性质保证 $V_t\setminus B_t$ 没有邻居落在 $V\setminus V_t$ 。所以，两份部分独立集若与袋的交集同为 $S$ ，任何未来选择对它们的兼容性都相同。它们已经选到的顶点数可以不同；正因为未来增量相同，较小的值才可被较大的值替换。这是保留最大值的依据，并不是说同一状态下的所有部分解原本一样大。

两支分别选中 a、d 和 a、f，通过共同袋 a、b 合并；共享的 a 只计一次，得到大小为三的独立集 — 共享边界的选择 a 在两份部分解中各计一次，join 必须减去一次

例子与边界

完整算例：十七个袋如何给出三个顶点

图与计算顺序

沿用树分解页的六顶点图

V=\{a,b,c,d,e,f\},\qquad E=\{ab,ac,bc,cd,ae,be,ef\}.

左右链从空叶开始，每一行的节点都是前一行的父亲； $L_6,R_6$ 汇合于 $J$ ，再经过 $A$ 到空根 $Z$ 。最大袋大小为 $3$ ，宽度为 $2$ 。下表列出全部 $17$ 个袋和全部子集状态。为了让表格易读，状态栏的 $ac$ 表示集合 $\{a,c\}$ ，其余字符串同理； $V_t$ 一栏也采用这个简写。

节点及操作	$B_t$	$V_t$	全部 $S:F_t(S)$
$L_0$ 空叶	$\varnothing$	$\varnothing$	$\varnothing:0$
$L_1$ 引入 $c$	$c$	$c$	$\varnothing:0,\ c:1$
$L_2$ 引入 $d$	$cd$	$cd$	$\varnothing:0,\ c:1,\ d:1,\ cd:-\infty$
$L_3$ 遗忘 $d$	$c$	$cd$	$\varnothing:1,\ c:1$
$L_4$ 引入 $a$	$ac$	$acd$	$\varnothing:1,\ a:2,\ c:1,\ ac:-\infty$
$L_5$ 引入 $b$	$abc$	$abcd$	$\varnothing:1,\ a:2,\ b:2,\ c:1$ ； $ab,ac,bc,abc:-\infty$
$L_6$ 遗忘 $c$	$ab$	$abcd$	$\varnothing:1,\ a:2,\ b:2,\ ab:-\infty$
$R_0$ 空叶	$\varnothing$	$\varnothing$	$\varnothing:0$
$R_1$ 引入 $e$	$e$	$e$	$\varnothing:0,\ e:1$
$R_2$ 引入 $f$	$ef$	$ef$	$\varnothing:0,\ e:1,\ f:1,\ ef:-\infty$
$R_3$ 遗忘 $f$	$e$	$ef$	$\varnothing:1,\ e:1$
$R_4$ 引入 $a$	$ae$	$aef$	$\varnothing:1,\ a:2,\ e:1,\ ae:-\infty$
$R_5$ 引入 $b$	$abe$	$abef$	$\varnothing:1,\ a:2,\ b:2,\ e:1$ ； $ab,ae,be,abe:-\infty$
$R_6$ 遗忘 $e$	$ab$	$abef$	$\varnothing:1,\ a:2,\ b:2,\ ab:-\infty$
$J$ 合并 $L_6,R_6$	$ab$	$abcdef$	$\varnothing:2,\ a:3,\ b:3,\ ab:-\infty$
$A$ 遗忘 $b$	$a$	$abcdef$	$\varnothing:3,\ a:3$
$Z$ 遗忘 $a$	$\varnothing$	$abcdef$	$\varnothing:3$

三个关键位置

在 $L_3$ 遗忘 $d$ 时，

F_{L_3}(\varnothing) =\max\{F_{L_2}(\varnothing),F_{L_2}(\{d\})\} =\max\{0,1\}=1.

袋里虽然没有选任何顶点，内部仍然选了 $d$ 。所以“空边界”绝不等于“空部分解”。接着引入 $a$ 时， $a$ 不邻接已选的 $d$ ，得到 $F_{L_4}(\{a\})=1+1=2$ 。

到合并节点，两支分别可以选 $\{a,d\}$ 与 $\{a,f\}$ 。它们的边界同为 $\{a\}$ ，于是

F_J(\{a\})=2+2-1=3.

不减一会错误地报告四个顶点；只考虑空边界又只能得到 $1+1=2$ ，漏掉真正最优解。表必须保留所有可能与未来兼容的边界选择，不能在合并前就把整张子表压成单个最大数。

最后遗忘 $b$ 时， $F_A(\varnothing)=\max\{2,3\}=3$ ，这里选的是 $J$ 的边界 $\{b\}$ ；而 $F_A(\{a\})=\max\{3,-\infty\}=3$ 。根再取二者最大，得到 $\alpha(G)=3$ 。

沿最优选择回溯

填表时在遗忘节点记录最大值来自哪一项。为明确一次平局的处理，在根的两个三分状态之间选择 $F_A(\{a\})$ 。 $A$ 随即选择 $F_J(\{a\})$ ，因为同时选 $a,b$ 不合法。 $J$ 向两个孩子都传递相同状态 $\{a\}$ 。

左支依次回到 $L_5$ 的 $\{a\}$ （不选 $c$ ）、 $L_4$ 的 $\{a\}$ （不选 $b$ ），在引入 $a$ 的位置确定选中 $a$ ，并进入 $L_3$ 的空边界。 $L_3$ 的值一来自 $L_2$ 的 $\{d\}$ ，因此选中 $d$ ；再回到 $L_1$ 的空边界，确定不选 $c$ 。右支完全对应地选中 $a,f$ ，不选 $b,e$ 。两支顶点集合求并，重复的 $a$ 只保留一次，得到

I=\{a,d,f\}.

若根的平局改选 $F_A(\varnothing)$ ，就会通过 $J$ 的 $\{b\}$ 找到 $\{b,d,f\}$ 。这也是全部两个最大独立集。可以不用 DP 再检查一次上界：选了 $a$ 或 $b$ 就不能选 $c,e$ ，最多再配 $d,f$ ，总共三个；若 $a,b$ 都不选，则边 $cd$ 与 $ef$ 各最多选一个端点，最多两个。

两种错误分解会怎样破坏计算

若在原图添加边 $df$ ，却保留上面的袋，边覆盖就失效：没有任何袋同时含 $d,f$ 。照旧执行局部转移仍会拼出 $\{a,d,f\}$ 并报告三，但它已不是独立集。新图实际最优值是二：选择 $a$ 或 $b$ 时， $d,f$ 不能兼得；两者都不选时， $c-d-f-e$ 构成路径，最多选两个。不存在跨内部边这一结论依赖合法分解，算法不能自行弥补遗漏的边。

运行交性质也不能省略。考虑仅有一个孤立顶点 $x$ 的图，让左右两支都从空袋引入 $x$ ，再遗忘为空袋，最后在空袋合并。顶点、边覆盖都满足，但 $x$ 的两组出现位置不连通。两支各给空边界值一，合并误算 $1+1=2$ ，实际图中只有一个顶点。运行交性质正是保证“两个内部没有同一个顶点”的条件。

推论与应用

状态数、存储与分解成本

设原图有 $n$ 个顶点、 $m$ 条边，给定的 nice 分解有 $q$ 个节点、宽度为 $k$ 。每袋至多枚举 $2^{k+1}$ 个子集。一个直接实现逐对检查子集内是否有边，每个状态用 $O((k+1)^2)$ 次邻接检查，然后执行常数次表查找与整数运算。因此，在读入图和建立所需邻接查询结构之后，安全的时间上界是

O\bigl(q(k+1)^2 2^{k+1}\bigr),

所有表与回溯选择占 $O(q2^{k+1})$ 个机器字。这里默认值 $0,\ldots,n$ 及不可行标记可用机器字表示；位掩码与袋间索引的处理至多再引入多项式于 $k$ 的因子。邻接查询的准备也要计费，例如用每个顶点的平衡搜索结构可在 $O((n+m)\log(n+1))$ 时间建立，并对所有袋内顶点对做 $O(q(k+1)^2\log(n+1))$ 次比较量级的预查询；预查询后填表只读袋内邻接矩阵。若使用哈希邻接表，这部分可取得相应的期望时间界。

本例实际只枚举 $57$ 项：左右支各 $25$ 项，合并袋 $4$ 项，最后两袋分别 $2,1$ 项。其中 $42$ 项可行、 $15$ 项无效，远小于统一上界 $17\cdot2^3=136$ 。顶点数六、袋数十七和状态数五十七分别计算不同的工作，不能混用。记录所有遗忘选择后，回溯只访问每个袋的一项，共 $O(q)$ 个选定状态；输出顶点时用全局标记去重即可。只保留少数活动表的节省空间策略，不能同时无条件声称保留了全部回溯信息。

若输入是含 $q_0$ 个节点的普通分解，可在不增加宽度的条件下，转成 $q=O((k+1)q_0)$ 个节点的 nice 分解，转换用时 $O((k+1)^2q_0)$ ；加入空叶和空根也在这个界内。[1] 不能直接把 $q_0$ 写成 $n$ 。在已给定 $O(n)$ 节点普通分解且采用适当的邻接预处理时，主体计算为 $2^k\operatorname{poly}(k)n$ ；若只给图，必须再加寻找分解的成本。较宽的启发式分解仍能得到正确答案，但控制状态数的是实际提供的宽度，不是尚未求出的最优树宽。

其他问题需要什么接口信息

独立集状态只需记录选择子集。求 Hamilton 环等问题时，未来还关心袋中哪些端点已由内部路径连通，通常必须记录连通分区；把本页的二进制状态直接移植过去并不充分。树宽限制接口大小，具体问题决定接口上必须保留什么。

参考资料

[1] Dániel Marx, Treewidth: Vol. 1, Lecture 11, 27 June 2023，逻辑幻灯片 12–14（PDF 页 24–30）：边界精确状态、nice 分解转换与独立集转移。原讲义采用单点叶；本文在其下增加空叶，并在顶端增加空根。

[2] Hans L. Bodlaender, Treewidth: Algorithmic techniques and results, Technical Report UU-CS-1997-31, 1997，§2、§4，尤其印刷页 8 的 Lemma 4.2：引入顶点只能接触孩子袋中的已有顶点。

[3] Marek Cygan et al., Parameterized Algorithms, Springer, 2015, Chapter 7：树宽参数化算法的进一步背景。

形式陈述 ​

状态的精确定义 ​

四类节点与正确性 ​

空叶与引入 ​

遗忘 ​

合并 ​

完整算例：十七个袋如何给出三个顶点 ​

图与计算顺序 ​

三个关键位置 ​

沿最优选择回溯 ​

两种错误分解会怎样破坏计算 ​

状态数、存储与分解成本 ​

其他问题需要什么接口信息 ​

反向链接