## Forbidden induced subgraphs and the price of connectivity for feedback vertex set

*Rémy Belmonte, Pim van 't Hof, Marcin Kamiński and Daniël Paulusma*

This paper appeared in the proceedings of MFCS 2014, the 39th International Symposium on Mathematical Foundations of Computer Science (held on August 25-27, 2014 in Budapest, Hungary), *Lecture Notes in Computer Science*, vol. 8635, pp. 57-68, 2014.

[__Preprint__][__DOI__]

### 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 Γ, the price of connectivity for feedback vertex set (poc-fvs) for Γ is defined as the maximum ratio cfvs(*G*)/fvs(*G*) over all connected graphs *G* in Γ. The poc-fvs for general graphs is unbounded, as the ratio cfvs(*G*)/fvs(*G*) can be arbitrarily large. We study the poc-fvs for graph classes defined by a finite family ℌ of forbidden induced subgraphs. We characterize exactly those finite families ℌ for which the poc-fvs for ℌ-free graphs is bounded by a constant. Prior to our work, such a result was only known for the case where |ℌ|=1.