论文标题
分类为$ h $ free Graphs的子集反馈顶点设置
Classifying Subset Feedback Vertex Set for $H$-Free Graphs
论文作者
论文摘要
在反馈顶点集问题中，我们的目标是在每个周期相交的图中找到一个小的$ s $顶点。子集反馈顶点集问题需要$ s $才能相交，仅包含某些指定集合$ t $的顶点的周期。我们还考虑了加权子集反馈顶点集问题，其中每个顶点$ u $具有权重$ w（u）> 0 $，我们要求$ s $的权重较小。通过将已知的NP硬度结果与新的多项式时间结果相结合，我们证明了子集反馈顶点集和加权子集反馈顶点的全部复杂性二分法，该二分法设置为$ h $ free Graphs，即，图形不包含图形$ h $作为诱导的子图。
In the Feedback Vertex Set problem, we aim to find a small set $S$ of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires $S$ to intersect only those cycles that include a vertex of some specified set $T$. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex $u$ has weight $w(u)>0$ and we ask that $S$ has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for $H$-free graphs, that is, graphs that do not contain a graph $H$ as an induced subgraph.
