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 generalization Subset Odd Cycle Transversal requires that S only intersects those odd cycles that include a vertex of a distinguished subset T of the vertex set . If we are also given weights for the vertices of the graph, we can ask instead that S has small weight: this is the problem Weighted Subset Odd Cycle Transversal. We prove an almost-complete complexity dichotomy for this problem when the input is restricted to graphs that do not contain a graph ~ H as an induced subgraph. In particular, we show that for (3P_1+P_2)-free graphs (where P_r is the path on r vertices) there is a polynomial-time algorithm, but the problem is NP-complete for 5P_1-free graphs, that is, graphs of independence number~4. Thus we obtain a dichotomy with respect to the independence number; this is an analogue of the dichotomy for Weighted Subset Feedback Vertex Set recently obtained by Papadopoulos and Tzimas. In contrast, Subset Feedback Vertex Set and Subset Odd Cycle Transversal have a polynomial-time algorithm for any graph class with bounded independence number. We also generalize the polynomial-time result of Papadopoulos and Tzimas for Weighted Subset Feedback Vertex Set on 4P_1-free graphs to (3P_1+P_2)-free graphs. As a consequence, we show that the complexity for both of the weighted subset transversal problems restricted to H-free graphs remains open for just three particular graphs~H .
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 .
D
generalization
R
requires that S only intersects
problem requires S to intersect only
R
subset T of the vertex set
vertex subset T
D
also
R
of the graph, we can
, we
R
this problem when the input is restricted to
Weighted Subset Odd Cycle Transversal for
D
~
R
In particular, we show that for (3P_1+P_2)-free graphs (where P_r is the path on r vertices) there is a polynomial-time algorithm, but the problem is NP-complete for 5P_1-free graphs, that is, graphs of independence number~4. Thus we obtain a dichotomy with respect to the independence number; this is an analogue of the dichotomy for
Our general approach can also be used for
R
recently obtained by Papadopoulos and Tzimas. In contrast, Subset Feedback Vertex Set and Subset Odd Cycle Transversal have a polynomial-time algorithm for any graph class with bounded independence number. We also generalize the polynomial-time
, which enables us to generalize a recent
D
for Weighted Subset Feedback Vertex Set on 4P_1-free graphs to (3P_1+P_2)-free graphs. As a consequence, we show that the complexity for both of the weighted subset transversal problems restricted to H-free graphs remains open for just three particular graphs~H