The price of connectivity for feedback vertex set
Rémy Belmonte, Pim van 't Hof, Marcin Kamiński and Daniël Paulusma
Discrete Applied Mathematics, vol. 217, no. 2, pp. 132143, 2017.
[DOI]
[Preprint]
The results presented in this paper appeared in preliminary form in:

the proceedings of Eurocomb 2013, the 7th European Conference on Combinatorics, Graph Theory and Applications (held on September 913, 2013 in Pisa, Italy), CRM Series, vol. 16, pp. 123128, 2013
[DOI], and in
 the proceedings of MFCS 2014, the 39th International Symposium on Mathematical Foundations of Computer Science (held on August 2527, 2014 in Budapest, Hungary), Lecture Notes in Computer Science, vol. 8635, pp. 5768, 2014 [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. The price of connectivity for feedback vertex set (pocfvs) for a class of graphs Γ is defined as the maximum ratio cfvs(G)/fvs(G) over all connected graphs G in Γ. We study the pocfvs for graph classes defined by a finite family ℌ of forbidden induced subgraphs. We characterize exactly those finite families ℌ for which the pocfvs for ℌfree graphs is upper bounded by a constant. Additionally, for the case where ℌ = 1, we determine exactly those graphs H for which there exists a constant c_{H} such that cfvs(G) ≤ fvs(G) + c_{H} for every connected Hfree graph G, as well as exactly those graphs H for which we can take c_{H} = 0.