@inproceedings { ,
title = {On the price of independence for vertex cover, feedback vertex set and odd cycle transversal},
abstract = {Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).},
conference = {43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).},
doi = {10.4230/lipics.mfcs.2018.63},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {63:1-63:15},
publicationstatus = {Published},
url = {https://durham-repository.worktribe.com/output/1145032},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2018},
author = {Dabrowski, K. K. and Johnson, M. and Paesani, G. and Paulusma, D. and Zamaraev, V.}
editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}
}