Tree Decomposition

给定图 , 的树分解是一颗树 , 其中 , 中的元素叫做 bag, 满足:

1. 对任意 , 则存在 使得
2. 对任意 , 存在 使得
3. 对任意 , 记 中包含 的 bag 的集合为 , 则 是 的一连通分支(一棵子树).

一种更规范的定义是, 树分解是二元组 , 其中 , 为指标集, 树 . 相当于在树分解后树的结点和bag 之间加了一个双射.

树分解 的宽度为 , 在 所有的树分解中最小的宽度称为 的树宽, 记作 .

容易验证至少有两个结点的树的树宽为 , 的树宽为 .

Path Decomposition

图 的 Path Decomposition 是满足 为链的树分解 , 因此可以记作 . 同样可以定义其宽度为 , 以及所有的 path decomposition 中最小的宽度记作 pathwidth . 显然 .

若 满足

• ;
• 或 成立, 其中 , . 这也是说进行路径分解后得到的路径中前一个 bag 总是比后一个 bag 多一个结点或者少一个结点.

则称这个路径分解是 好 (nice) 的.

Problems on graphs with bounded pathwidth

MAX-CUT

对于 , 其最大割指的是最大化 之间的边数的集合 . 现在借助路径分解以及动态规划给出一个结果, 记 为 中 之间的边的集合, 即 给定 的一个宽度至多为 的路径分解, 在线性时间内可以得到好的宽度为 的路径分解 , 记 , 则 .

对于某个 , 令 为 的一个划分, 那么 可以确定一些 的划分 , 满足 . 记 其中 为 的边集.

那么就需要求 首先考虑边界 , 此时设 , 则 , 此时 , 则对任意 , .

然后根据好的路径分解的定义, 自然要分两种情况考虑:

• , 则 的所有划分根据 的位置可以分为两类, 对 的某个划分 , 若 , 则 是 的一个划分,

Counting Perfect Matchings

Minimum Bisection

Maximum Independent Set

Minimum Dominating Set

Exercise

1. 有关 separator
2. 给定路径分解在线性时间内求出好的路径分解

极大 co-1-plex 的数目等于极大 induced matching 的个数.

设 , 对于 , 是独立集或空集(不存在 induced matching), 则 , 两者是一一对应的.

能不能估计 的大小?

一定有 .