License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9645/
Go to the corresponding LIPIcs Volume Portal

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:
LIPIcs-MFCS-2018-63.pdf (0.4 MB)

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
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI