Skip to main content

Research Repository

Advanced Search

Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set

Belmonte, R.; Hof, van 't P.; Kaminski, M.; Paulusma, D.

Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set Thumbnail


Authors

R. Belmonte

van 't P. Hof

M. Kaminski



Contributors

Ersébet Csuhaj-Varjú
Editor

Martin Dietzfelbinger
Editor

Zoltán Ésik
Editor

Abstract

Let fvs(G) and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. For a graph class G, the price of connectivity for feedback vertex set (poc-fvs) for G is defined as the maximum ratio cfvs(G)/fvs(G) over all connected graphs G in G. It is known that the poc-fvs for general graphs is unbounded. We study the poc-fvs for graph classes defined by a finite family H of forbidden induced subgraphs. We characterize exactly those finite families H for which the poc-fvs for H-free graphs is bounded by a constant. Prior to our work, such a result was only known for the case where |H|=1.

Citation

Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2014). Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29 August 2014 ; proceedings, Part II (57-68). https://doi.org/10.1007/978-3-662-44465-8_6

Conference Name 39th International Symposium, MFCS 2014
Conference Location Budapest, Hungary
Publication Date Jan 1, 2014
Deposit Date Dec 20, 2014
Publicly Available Date Mar 29, 2024
Pages 57-68
Series Title Lecture notes in computer science
Series Number 8635
Series ISSN 0302-9743,1611-3349
Book Title 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29 August 2014 ; proceedings, Part II.
ISBN 9783662444641
DOI https://doi.org/10.1007/978-3-662-44465-8_6
Public URL https://durham-repository.worktribe.com/output/1154514

Files





You might also like



Downloadable Citations