【学习笔记】树分解算法

树分解的概念是 Roberson 和 Seymour 在 1986 年提出的。在树宽度有界的图上，许多 NPC 问题得到了基于树分解的线性算法。这其中包括了3染色问题，最大团问题等经典问题。 本文将会对这个算法进行介绍。由于偏向理论，因此不会有任何代码。~~实际上是退役了懒得写~~ 需要说明的是，这个算法在OI中并无很大的实际作用。~~属于是根据这个出题要被骂的程度~~。如果只是为了考试目的并不需要学习这种科技，图一乐可以看看。可能会出现一些细节上的错误，欢迎指出。 ## 1 树分解 ### 1.1 定义 考虑给出 **树分解(tree decomposition)** 和 **树宽度(tree-width)** 的定义。 对于简单图 $G=(V,E)$，其**树分解**是 $\mathcal D=(\mathcal T,(B_t)_{t\in T})$，其中 $\mathcal T=(T,F)$ 是一颗有根树，$T$ 为其点集，$F$为其边集。$(B_t)_{t\in T}$ 是一个 $V$ 的子集族。其满足以下条件： + $\forall v\in V$， $B^{-1}(v):=\{t\in T|v\in B_t\}$，即包含$v$的顶点集合非空且在 $\mathcal T$ 中联通（此处将 $\mathcal T$ 视作无向图）。 + $\forall \{v,w\}\in E$， 存在 $t\in T$ 使得 $v,w\in B_t$。 **树分解的宽度**是 $$\max\left\{|B_t|\big|t\in T\right\}-1$$ $G$ 的**树宽度** $\operatorname{tw}(G)$ 是 $G$ 的树分解宽度的最小值。 如果对 $\{v,w\}\in E$，有 $v,w\in B_t$，那么我们称 $\{v,w\}$ 被包 $B_t$ **实现**了。不难发现任何一条边都被至少一个包实现。 --- ### 1.2 相关性质 注意到一些关于树宽度的事实： + 一棵树的树宽度是 $1$ 有一个比较明显的构造，就是将一个点 $v$ 及其父亲作为一个包然后用这个包去代替原树中的 $v$。 + 任意环的树宽度是 $2$ 构造类似上一个，而没有宽度为 $1$ 的树分解是因为假如有可以推出树分解成环，~~具体懒得写了~~。 + 任意点数为 $k$ 的完全图树宽度为 $k-1$ 证明也比较简单就懒得写了。大致是可以假设存在树宽度小于 $k-1$ 的树分解，可以利用所有边被包实现的性质找到和 $B^{-1}(v)$ 联通的性质的矛盾。~~这放书上不得是一个练习再加一个hint~~。有兴趣可以自己证明一下。 ## 2 基于树分解的算法 对于固定自然数 $w$ ，存在一个线性时间的算法对所有满足 $tw(G)\leq w$ 的图 $G$ 输出它的一个最大独立集。 ### 树分解诱导的子图 给定图 $G$ 和它的树分解 $TD=(T,(B_t)_{t\in V(T)})$满足 $width(TD)\leq w$。 对任意 $t\in V(t)$: + $G_t^0$ 是由 $B_t$ 诱导的子图 。 + $G_t$ 是由对于 $t$ 为根的子树 $T_t$ 的$\bigcup\limits_{t'\in T_t}B_t$ 所诱导的子图 --- 基于这个定义，令 $son_t$ 表示 $t$ 的儿子节点集合，考虑这样一个动态规划： $dp(t,X)$ 表示 $X\subseteq B_t$ 且 $X$ 为独立集时满足 $I\cup B_t=X$ 的 $G_t$ 的独立集 $I$ 的大小最大值。 我们考虑固定 $B_t$ 内的独立集，那么就由树分解含相同点的包之间联通的性质可以得到不在 $B_t$ 内的点是独立的，这就为动态规划中可以自由拼接独立集形成了基础。 最终可以得到我们的DP柿子： $$dp(t,X)=|X|+\sum_{t'\in son_t}\max\limits_{X'\cap B_t=X\cap B_{t'}}\{dp(t',X')-|X\cap X'|\}$$ 这样我们就得到了一个 $\mathcal O(n2^{2w})$ 的算法，在 $w$ 有上界的时候就是 $\mathcal O(n)$ 。 ## 3着色问题 给定 图 $G=(V,E)$。它的一个3着色是个函数 $f:V\to\{1,2,3\}$ 满足对所有的边 $(u,v)\in E$ 我们都有 $f(v)\neq f(u)$ 这实际上是一个NPC问题，但是在 $w$ 有上界的时候依然有高效算法。 还是利用边的关系只需要在父子节点之间考虑，我们考虑动态规划 $$dp(t)=\{f|f\text{为}G_t^0\text{的}3\text{着色且可以扩充为}G_t\text{的}3\text{着色}\}$$ 那么在转移的时候只需要考虑某个方案是否会和某一子节点的所有方案都矛盾即可。