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.