Skip to main content

Research Repository

Advanced Search

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

Dabrowski, K. K.; Johnson, M.; Paesani, G.; Paulusma, D.; Zamaraev, V.

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


Authors

K. K. Dabrowski

G. Paesani

V. Zamaraev



Contributors

Igor Potapov
Editor

Paul Spirakis
Editor

James Worrell
Editor

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

Citation

Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (63:1-63:15). https://doi.org/10.4230/lipics.mfcs.2018.63

Conference Name 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
Conference Location Liverpool, UK
Start Date Aug 27, 2018
End Date Aug 31, 2018
Acceptance Date Jun 25, 2018
Publication Date Jan 1, 2018
Deposit Date Jul 30, 2018
Publicly Available Date Mar 29, 2024
Pages 63:1-63:15
Series Title Leibniz International Proceedings in Informatics
Series Number 117
Series ISSN 1868-8969
Book Title 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
DOI https://doi.org/10.4230/lipics.mfcs.2018.63
Public URL https://durham-repository.worktribe.com/output/1145032

Files






You might also like



Downloadable Citations