论文标题
史坦纳树的遗传图课程：树宽的视角
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
论文作者
论文摘要
我们考虑了经典问题（边缘）施泰纳树和顶点施泰纳树之后，将输入限制为以一组禁止诱导的子图表为特征的一类图表。我们显示了以前问题的二分法，仅限于$（h_1，h_2）$ - 免费图表和后一个问题的二分法，仅限于$ h $ free图。我们发现存在一个无限的图形$ h $的家族，因此顶点steiner树是$ h $ free Graphs的多项式时间求解，而仅存在两个图形$ h $，它可以容纳Edge Steiner树。我们还发现，Edge Steiner树是$（H_1，H_2）$的多项式时间解决，并且仅当$（H_1，H_2）$的类树宽度时，免费图形是有限的（by P $ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ neq $ np）。为了获得后一个结果，我们确定所有对$（H_1，H_2）$的所有对（H_1，H_2）$ - 免费图具有有限的TreeWidth。
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to $(H_1,H_2)$-free graphs and a dichotomy for the latter problem restricted to $H$-free graphs. We find that there exists an infinite family of graphs $H$ such that Vertex Steiner Tree is polynomial-time solvable for $H$-free graphs, whereas there exist only two graphs $H$ for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for $(H_1,H_2)$-free graphs if and only if the treewidth of the class of $(H_1,H_2)$-free graphs is bounded (subject to P $\neq$ NP). To obtain the latter result, we determine all pairs $(H_1,H_2)$ for which the class of $(H_1,H_2)$-free graphs has bounded treewidth.
