Pim van 't Hof

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. 132-143, 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 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].

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 (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 c_H such that cfvs(G) ≤ fvs(G) + c_H for every connected H-free graph G, as well as exactly those graphs H for which we can take c_H = 0.