The price of connectivity for feedback vertex setRémy Belmonte, Pim van 't Hof, Marcin Kamiński and Daniël Paulusma
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 9-13, 2013 in Pisa, Italy), CRM Series, vol. 16, pp. 123-128, 2013
[DOI], and 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 [DOI].
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 (poc-fvs) for a class of graphs Γ is defined as the maximum ratio cfvs(G)/fvs(G) over all connected graphs G in Γ. 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 upper bounded by a constant. Additionally, for the case where |ℌ| = 1, we determine exactly those graphs H for which there exists a constant cH such that cfvs(G) ≤ fvs(G) + cH for every connected H-free graph G, as well as exactly those graphs H for which we can take cH = 0.