The Price of Connectivity for Feedback Vertex Set

Rémy Belmonte, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma

Published 2015-10-09Version 1

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 ${\cal G}$ is defined as the maximum ratio $\mbox{cfvs}(G)/\mbox{fvs}(G)$ over all connected graphs $G\in {\cal G}$. We study the poc-fvs for graph classes defined by a finite family ${\cal H}$ of forbidden induced subgraphs. We characterize exactly those finite families ${\cal H}$ for which the poc-fvs for ${\cal H}$-free graphs is upper bounded by a constant. Additionally, for the case where $|{\cal H}|=1$, we determine exactly those graphs $H$ for which there exists a constant $c_H$ such that $\mbox{cfvs}(G)\leq \mbox{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$.