树分解是图子式理论中发展起来的一个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。

引入–树上的独立集问题

树上的独立集问题–贪心算法

首先，我们证明：

定理: 如果 $T=(V,E)$ 是一棵树，$v$ 是 $T$ 的一片叶子，那么存在包含 $v$ 的最大独立集。

证明: 考虑最大独立集 $S$, 设 $e=(u,v)$ 是唯一与 $v$ 相连的边。显然，$u$ 与 $v$ 至少有一个在 $S$ 中：否则，可以把 $v$ 加入 $S$，使 $S$ 变大。如果 $v\in S$，定理成立；如果 $u\in S$，则从 S 中删除 $u$ 插入 $v$，可以得到一个相同大小的独立集。

因此，我们可以通过选择树中的叶节点，删除与它关联的顶点和边，来获得树的最大独立集。删除叶节点的父节点后树可能会变得不连通，只需要对得到的森林分别进行相同的算法。

image-20200630135548997

这个贪心算法可以解决在一般图上的 NP-hard 问题。

此外，对于一般图，当图中存在叶节点时，这个定理也是成立的。当在解决独立集问题时，可以启发式地允许这个算法直至找不到一个叶节点，从而缩小图的规模使后续的算法更容易进行。

树上的最大权独立集–动态规划

对于树上的最大权独立集问题，可以用动态规划求解：

用 $\text{OPT} _ {in}(u)$ 表示子树 $T_u$ 包含 $u$ 的独立集最大权, 用 $\text{OPT} _ {out}(u)$ 表示子树 $T_u$ 不包含 $u$ 的独立集最大权，有：
$$
\text{OPT}_ {in}(u) = \omega _ u + \sum_{v\in \text{children}(u)} \text{OPT} _ {out}(v)
$$

$$ \text{OPT} _ {out}(u) = \sum_{v\in \text{children}(u)} \max(\text{OPT} _ {out}(v),\text{OPT} _ {in}(v)) $$

因此，我们可以用动态规划的方法求解树上的最大权独立集问题。

image-20200630135524453

思考

定性的理解，当图是树型结构时，考虑节点 $v$, $v$ 结点将树分为两部分：以 $v$ 为根节点的子树和其余部分。两个部分之间的影响只会通过节点 $v$ 传递。因此，通过考虑节点 $v$ 在解中出现的不同方式，可以将子树的问题与其余部分的问题分开，独立解决。

我们可以希望图有一个弱一点的性质：可以用小的结点集合递归地将图切开，使得切开的多个部分不会有相互影响。

树宽的定义

树分解的定义

看下面这个图，(a) 和 (b) 同一个图的两种画法，通过 (b) 可以看出图中的边是由十个三角形组出。(c) 说明了这 10 个三角形是如何连接的，它看起来是树型的。

image-20200630143527745

为了精确地表达这种性质，我们定义图的树分解：

$G=(V,E) $ 的树分解由树 $T$ 和片段集 ${V_t, t\in T}$ 组成，其中$V_t\subseteq V$ 是图的顶点集的子集。树 $T$ 和片段集 ${V_t, t\in T}$ 满足：

  • (顶点覆盖) $G$ 的每一个顶点至少属于一个片段 $V_t$
  • (边覆盖) 对 $G$ 的每一条边 $e$，存在一个片段 $V_t$ 包含 $e$ 的两个端点
  • (一致性) 设 $t_1$, $t_2$ 和 $t_3$ 是 $T$ 的 3 个顶点， $t_2$ 在 $t_1$ 到 $t_3$ 的路径上，如果 $G$ 的顶点 $v$ 属于 $V_{t_1}$ 和 $V_{t_3}$，则它也属于 $V_{t_2}$

可以验证，用10个三角形作为片段，图 (c) 中的树是 (a,b) 中图的树分解。

树分解的性质

定理 1: 假设 $T-t$ 有分支 $T_1, …, T_d$，那么子图 $G_{T_1}-V_t, G_{T_2}-V_t, …, G_{T_d}-V_t $ 没有共同的结点，且它们之间没有边。

image-20200630161045228

定理 2: 设 $X$ 和 $Y$ 是删去边 $(x,y)$ 后 $T$ 的两个分支，那么从 $V$ 中删去集合 $V_x\cap V_y$ 把 $G$ 拆分成两个子图 $G_X-(V_x\cap V_y)$ 和 $G_Y-(V_x\cap V_y)$，这两个子图没有共同的顶点，并且没有一条边的两个端点分别在这两个子图中。

image-20200630161814372

非冗余的树分解：不存在边 $(x,y)$ 使得 $V_x \subseteq V_y$。可以将冗余的树分解逐步合并得到一个非冗余的树分解。

定理 3: $n$ 个顶点的图的任意非冗余的树分解最多有 $n$ 个片段。

证明: 对于 $T$ 上的叶子 $t$， $V_t$ 中至少有一个结点不在其他片段中出现。

树宽的定义

我们定义树分解 $(T,{V_t})$ 的宽度为所有片段 $V_t$ 的大小的最大值减 1

$$
\text{width} (T,{V_t}) = \max_t\vert V_t\vert -1
$$

图 10.5 中的图树宽为 2.

定理: 连通图 $G$ 的树宽为 1 当且仅当它是树。

树分解上的动态规划

给定 $n$ 个顶点的图及其宽度为 $\omega$ 的树分解 $(T,{V_t})$，我们希望得到一个运行时间为 $O(f(\omega)\cdot n)$ 的算法，其中 $f(x)$ 是仅依赖于 $\omega$ 的指数函数，而与顶点数无关。

一个想法是模拟树上的动态规划算法，从 $T$ 的叶节点向上考虑每个片段，对结点 $t$, 我们枚举 $V_t$ 与最优解可能的交集，即枚举 $V_t$ 的所有为独立集的子集，有 $2^{\omega +1}$ 种可能，在选取这些点的假设下对问题的其他部分进行求解。

以最大权独立集为例，符号说明：

  • 为顶点集 $V$ 的子集 $V’$，用 $\omega(V’) $ 表示 $V’$ 中所有顶点的权重和，$\omega(V’) = \sum_{v\in V’} \omega_v$
  • 确定树 $T$ 的根节点 $r$，对任意的顶点 $t$, 用 $T_t$ 表示以 $t$ 为根节点的子树， $G_t$ 表示 $T_t$ 中所有顶点对应的片段中的顶点构成的 $G$ 的子图。
  • 对 $T$ 中的顶点 $t$，用 $t_1,…,t_d$ 表示 $t$ 的子节点
  • 算法中， $U$ 表示 $t$ 对应的片段 $V_t$ 与最优解可能的交集， $U_i$ 表示 $t$ 的子节点 $t_i$ 对应的片段 $V_{t_i}$ 与最优解可能的交集
  • $f_t(U)$ 表示当 $t$ 对应的片段 $V_t$ 中选择了 $U$ 这个子集时，以 $t$ 为根节点的子树 $T_t$ 的最优解的权重; 同样的，$f_{t_i}(U_i)$ 表示子树 $T_{t_i}$ 选择 $U_i$ 时的最优解的权重

$f_t(U)$ 由递推式给出：

$$
f_t(U) = \omega(U) + \sum_{i=1}^d \max_{U_i} \{f_{t_i}(U_i)-\omega(U_i\cap U): U_i \cap V_t = U\cap V_{t _ i} 且 U_i\subseteq V_{t_i} 是独立集\}
$$

其中，$U_i \cap V_t = U\cap V_{t_i}$ 保证了不会出现同时在两个片段中的顶点在 $U$ 中选中而没有出现在 $U_i$ 中的情况。动态规划的算法为：

image-20200701160935623

可以得到算法的时间复杂度为 $O(4^{\omega+1}\omega n)$

构造树分解

确定一个图的树宽是 NP-hard 的，但我们可以得到一个算法：给定图 $G$ 和树宽 $\omega$, 算法在 $O(f(\omega) \cdot mn)$ 时间内得到一个宽度小于 $4\omega$ 的树分解，或返回图 $G$ 不存在树宽小于 $\omega$ 的树分解的结论。（也就是一个近似比为 4 的算法）

首先，我们希望可以得到一种结构，如果图中存在这种结构，则不可能存在小的树宽。我们提出下面的定义：

  • 可分离的：给定两个大小相同的集合，存在一个严格比他们小的集合使它们完全不连接，则称这两个集合是可分离的。也就是说, 对 $Y,Z\subseteq V$, 存在 $S\subset V, \vert S\vert < \vert Y\vert = \vert Z\vert$ 且 $G-S $ 中没有从 $Y-S $ 到 $Z-S$ 的路径，则称 $Y,Z$ 是可分离的
  • $\omega-$连接：$G$ 中的节点集 $X$, 如果 $\vert X\vert \ge \omega$ 且 $X$ 不包含可分离子集 $\vert Y\vert = \vert Z\vert \le \omega $

定理: 设 $G=(V,E)$ 有 $m$ 条边，$X$ 是 $G$ 中 $k$ 个顶点的集合，$\omega\le k$ 给定，可以在 $O(f(k)\cdot \omega)$ 内确定 $X$ 是否是 $\omega-$连接的，如果不是，则可以得到 $\vert Y\vert = \vert Z\vert \le \omega$ 被集合 $S$ 分离。

证明: 只需遍历 $X$ 的所有子集对。对每对子集 $Y$, $Z$，它们可分离当且仅当不存在 $\vert Y\vert = \vert Z\vert$ 条顶点不交的路径，其中每条路径的一个端点在 $Y$ 中，另一个端点在 $Z$ 中。这个问题是一个带顶点容量的无向图最大流问题。

定理: 如果 $G$ 包含不小于 $3\omega$ 的 $(\omega+1)-$连接集，则 $G$ 的树宽大于等于 $\omega$

详细证明见书。直观的理解，树宽小于 $\omega$ 会有大小小于等于 $(\omega+1)$ 的片段将集合分离，因此不可能存在 $(\omega+1)-$连接集。

算法

构造树分解算法的直观是从第一个片段开始，希望剩余的部分被分为不连接的分支，递归地进入每个分支，加入新的片段进一步引起图的分裂，直到得到最后的片段。

image-20200701175320969

用 $U\subseteq V$ 表示 $G$ 中属于已构造好的片段的顶点集合，此时，树 $T$ 与片段集 ${V_t}$ 构成了 $U$ 的一个树分解。

设 $C$ 是 $G-U$ 的一个连通分支，$u\in U$，如果存在一个顶点 $v\in C$ 有一条边与 $u$ 相连，则称 $u$ 是 $C$ 的一个邻点。算法保证

  • 在算法执行中， $G-U$ 的每一个连通分支 $C$ 最多有 $3\omega$ 个邻点，且存在一个片段 $V_t$ 包含所有的邻点。

算法保证在树分解中添加新顶点与新片段，满足上述条件的同时 $U$ 至少增加一个顶点，从而最多进行 $n$ 次迭代，结束时得到图 $G$ 的树分解。

设 $C$ 是 $G-U$ 的任意一个连通分支，$X$ 是 $U$ 中 $C$ 的邻点集。则 $X$ 最多有 $3\omega$ 个顶点，且存在一个片段 $V_t$ 包含整个$X$ 。

  • 若 $\vert X\vert < 3\omega$， 对 $C$ 中的任意顶点 $v$ , 定义新的片段 $V_s = X\cup {v}$，$T$ 中新的顶点 $s$ 是 $t$ 的子节点，可以证明此时得到的部分树分解仍满足条件，且 $U$ 增加一个顶点

  • 若 $\vert X\vert = 3\omega$，首先检查 $X$ 是不是 $(\omega+1)-$连接集。如果是，则算法返回 $G$ 的树宽大于等于 $\omega$。如果 $X$ 不是 $(\omega+1)-$连接集，则得到集合 $Y,Z\subseteq X, S\subseteq V$ 满足 $\vert S\vert <\vert Y\vert = \vert Z\vert \le \omega +1$ 且在 $G-S $ 中没有从 $Y-S $ 到 $Z-S$ 的路径。

    记 $S’ = S\cap(Y\cup Z\cup C)$ ，定义一个新片段 $V_s = X\cup S’$，$T$ 中新的顶点 $s$ 是 $t$ 的子节点，$\vert X\cup S’ \vert\le 3\omega + \omega = 4\omega$ ，满足条件； $S’\cap C$ 非空， $U$ 至少增加一个顶点；下面还需证明 $C$ 最多有 $3\omega$ 个邻点：

    原来的分支 $C$ 可能被分解为多个分支 $C’\subseteq C, C’\subseteq G-(U\cup S’)$ ，每一个分支 $C’$ 的邻点都在 $X\cup S’$ 中，我们可以证明所有的邻点都在 $(X-Z)\cup S’$ 或 $(X-Y)\cup S’$ 中，这两个子集都小于 $3\omega$, 否则， $G-S $ 中存在一条从 $Y-S $ 到 $Z-S$ 的路径，矛盾。

可以得到这个算法的时间复杂度为 $O(f(\omega) \cdot mn)$

参考资料：

《Algorithm Design》Jon Kleinberg, Eva Tardos， Chapter 10

最后编辑：2020-07-01