2026-07-21T19:26:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9645 2024-03-06T10:44:37Z ddc:004 open_access

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal Dabrowski, Konrad K. Johnson, Matthew Paesani, Giacomo Paulusma, Daniël Zamaraev, Viktor vertex cover feedback vertex set odd cycle transversal price of independence 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konrad K. Dabrowski and Matthew Johnson and Giacomo Paesani and Daniël Paulusma and Viktor Zamaraev 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.63 urn:nbn:de:0030-drops-96452 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.63 eng https://creativecommons.org/licenses/by/3.0/legalcode