Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.63
URN: urn:nbn:de:0030-drops-96452
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9645/
Dabrowski, Konrad K. ; Johnson, Matthew ; Paesani, Giacomo ; Paulusma, Daniël ; Zamaraev, Viktor
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
| pdf-format: |
|
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).
BibTeX - Entry
@InProceedings{dabrowski_et_al:LIPIcs:2018:9645,
author = {Konrad K. Dabrowski and Matthew Johnson and Giacomo Paesani and Dani{\"e}l Paulusma and Viktor Zamaraev},
title = {{On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {63:1--63:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9645},
URN = {urn:nbn:de:0030-drops-96452},
doi = {10.4230/LIPIcs.MFCS.2018.63},
annote = {Keywords: vertex cover, feedback vertex set, odd cycle transversal, price of independence}
}
| Keywords: | vertex cover, feedback vertex set, odd cycle transversal, price of independence | |
| Seminar: | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 27.08.2018 |
