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

This paper appeared 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][Preprint]

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. In general graphs, the ratio cfvs(G)/fvs(G) can be arbitrarily large. We study the interdependence between fvs(G) and cfvs(G) in graph classes defined by excluding one induced subgraph H. We show that the ratio cfvs(G)/fvs(G) is bounded by a constant for every connected H-free graph G if and only if H is a linear forest. We also 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.