论文标题
计算加权子集横向$ h $ free图
Computing Weighted Subset Transversals in $H$-Free Graphs
论文作者
论文摘要
对于奇数循环横向问题，任务是在图中找到一个小的$ s $顶点，该顶点与每个奇数长度相交。子集奇数循环横向问题需要S仅与包括杰出顶点子集$ t $的顶点的奇数相交。如果我们给出了顶点的权重，我们会问$ s $的权重很小：这是问题加权子集奇数循环横向。我们证明，对于不包含图形$ h $作为诱导子图的图形的加权子集奇数周期横向横截面，我们证明了几乎完全完整的复杂性二分法。我们的一般方法也可以用于加权子集反馈顶点集，这使我们能够推广帕帕多普洛斯和tzimas的最新结果。
For the Odd Cycle Transversal problem, the task is to find a small set $S$ of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of a distinguished vertex subset $T$. If we are given weights for the vertices, we ask instead that $S$ has small weight: this is the problem Weighted Subset Odd Cycle Transversal. We prove an almost-complete complexity dichotomy for Weighted Subset Odd Cycle Transversal for graphs that do not contain a graph $H$ as an induced subgraph. Our general approach can also be used for Weighted Subset Feedback Vertex Set, which enables us to generalize a recent result of Papadopoulos and Tzimas.
