路径宽

路径宽衡量一张图能否沿一个线性顺序分批处理，同时只需保留较少的顶点信息。它以路径分解为基础，是树分解在分解结构必须为路径时得到的参数。

路径分解

设有限无向图为 $G=(V,E)$。路径分解是一列顶点集合 $B_1,\dots ,B_m$，称为袋，满足三个条件：

• 每个顶点至少出现在一个袋里。
• 每条边的两个端点至少共同出现在一个袋里。
• 对每个顶点 $v$，含 $v$ 的袋的位置形成连续区间：若 $v\in B_i\cap B_k$ 且 $i<j<k$，则 $v\in B_j$。

分解的宽度是 $\underset{i}{max}|B_i|-1$，图的路径宽 $\mathrm{pw}(G)$ 是所有路径分解宽度的最小值。减一是常用约定；单个顶点图的路径宽于是为零。

四环的一个分解

对四环 $1-2-3-4-1$，取 $$B_1=\{1,2,4\},B_2=\{2,3,4\}.$$ 边 $12,14$ 在第一个袋中，边 $23,34$ 在第二个袋中。顶点 2、4 出现在两个相邻袋中，其余顶点各出现一次，因此连续性也成立。最大袋大小为 3，宽度为 2，故路径宽不超过 2。

两个袋覆盖四环的全部边；每个顶点出现的位置连续。

这个上界也是最优的。反设存在宽度至多 1 的分解，则每个袋至多含两个顶点。把每个顶点出现的袋位置看作一个整数区间，并在四个区间中选右端最靠左的一个，设它属于顶点 $v$。$v$ 的两个环邻居分别与它相邻，故它们各自的区间都与 $v$ 的区间相交。由于所选区间的右端最靠左，这两个邻居的区间都包含该右端位置。因此那个袋同时包含 $v$ 及其两个邻居，至少有三个顶点，矛盾。故 $\mathrm{pw}(C_4)=2$。

与算法的关系

连续性保证一个顶点一旦不再出现在后续袋里，就不会突然再次出现。动态规划沿袋序处理时，可以在当前袋保存与尚未处理部分有关的状态。状态数量通常随袋大小增长；实际复杂度还取决于具体问题和状态设计。

每个路径也是树，所以任何路径分解都是树分解，因而 $\mathrm{tw}(G)\le \mathrm{pw}(G)$。允许分解树分支可能得到较小的宽度；不能把两个参数当成定义相同。