On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani +2

Let $vc(G)$, $fvs(G)$ and $oct(G)$, respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph $G$. One can a…