Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.

Dabrowski, K.K. and Johnson, M. and Paesani, G. and Paulusma, D. and Zamaraev, V. (2018) 'On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.', in 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 63:1-63:15. Leibniz International Proceedings in Informatics. (117).

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).

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(442Kb)
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
(442Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.4230/LIPIcs.MFCS.2018.63
Publisher statement:© Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Viktor Zamaraev; licensed under Creative Commons License CC-BY
Date accepted:25 June 2018
Date deposited:31 July 2018
Date of first online publication:2018
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar