论文标题
$ h $ free图中的计算子集横向
Computing Subset Transversals in $H$-Free Graphs
论文作者
论文摘要
我们通过将输入限制为$ h $ free Graphs，即不包含某些固定图〜$ H $作为诱导的子图的图形来研究两个众所周知的图形横向问题的计算复杂性，即子集反馈顶点集和子集奇数横向。通过结合已知结果和新结果，我们确定了每个图$ h $ $ h $ free Graphs上这两个问题的计算复杂性，除非$ h = sp_1+p_4 $对于某些$ s \ geq 1 $。作为我们方法的一部分，我们介绍了子集顶点封面问题，并证明它是$（sp_1+p_4）$的多项式时间解决方案 - 每$ s \ geq 1 $的免费图。
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed graph~$H$ as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on $H$-free graphs for every graph $H$ except when $H=sP_1+P_4$ for some $s\geq 1$. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for $(sP_1+P_4)$-free graphs for every $s\geq 1$.
