树分解中的分隔符概念是什么？

Question

我试图使用动态规划来理解树分解中的最大独立集问题。然而，我无法在所提出的算法中理解“分隔符”的概念。有人可以让我清楚这一点吗？提前致谢。

Answer 1

分隔符是顶点的子集，删除这些顶点后会留下具有多个连接组件的图。如果每个连接组件的顶点数少于原始图的一半，则分隔符是平衡的。

树宽较小的图具有较小的平衡分隔符。更准确地说，树宽为 k 的图具有最多包含 k+1 个顶点的平衡分隔符。

算法利用这一点如下：

• 从图表中删除一个小的平衡分隔符

• 递归地找到连接组件的最佳解决方案

• 再次添加分隔符（可能逐个顶点），并使用连接组件的解来找到整个图的最佳解。

为了使上述方案高效，需要满足一些要求：

• 第一步中的分隔符很小（即大小恒定）

• 第二步中的连通分量的顶点数量比原始图少得多（即，恒定分数，例如1/2）。

• 上述属性被继承到诱导子图（否则你无法有效地递归）

• 连接分量的部分最优解可以有效地组合成整个图的最优解

这些要求可以通过低树宽图来满足 - 除了最后一个：这个是特定于每个优化问题的，这就是算法设计者撰写研究论文的内容。

（图片取自维基百科关于顶点分隔符的文章。）