图的宽度参数

图的宽度参数是一类用于衡量图的结构复杂性的度量，它们通过考察图的某种特定分解方式（如树分解、分支分解）来定义。这些参数在算法设计中尤为重要，因为许多NP-难问题在宽度参数有界的图上可以在多项式时间内求解。

1. 基本思想：宽度参数的核心思想是将图“铺展”成一种树状结构（分解），并衡量这种分解的“宽度”，即分解中任一单元所包含的图元素（顶点或边）的最大数量。一个较小的宽度值意味着图在结构上接近树，因此可能允许高效的算法。

2. 树宽：树宽是最经典的宽度参数。一个图的树分解由一棵树和一系列与树节点相关联的顶点子集（称为袋）组成，满足：每个顶点出现在至少一个袋中；每条边的两个端点出现在同一个袋中；对于任一顶点，包含它的所有袋在树中形成一个连通子树。树宽定义为所有袋的大小的最大值减1。树的树宽为1，环的树宽为2。

3. 路径宽：如果树分解中的树被限制为一条路径，则得到路径分解，其宽度（路径宽）定义为所有袋的大小的最大值减1。路径宽不大于树宽，但反之不成立。路径宽小的图具有线性结构。

4. 分支宽：分支宽关注边的分解。一个图的分支分解是一棵根树，其叶子对应于图的边。树中的每条边将叶子集划分为两部分，对应于图的一个边割。分支宽是该边割中顶点的最小数量（即割的顶点边界的大小）在所有分解边上的最大值。分支宽与树宽紧密相关，两者相差不超过常数因子。

5. 聚类宽：聚类宽通过一系列图操作（如顶点不相交的并、重标顶点、添加边等）来定义图的复杂度。它衡量生成图所需的不同顶点标签的数量。聚类宽在稠密图上可能比树宽更有界，适用于描述具有重复模块化结构的图。

6. 算法意义：对于树宽、路径宽或聚类宽有界的图类，许多NP-难问题（如独立集、着色、哈密顿路径）存在固定参数可解算法。这意味着若宽度参数为常数，问题可在关于图大小的多项式时间内求解，尽管可能对参数指数依赖。这使得宽度参数成为参数复杂性理论的核心工具。