The Price of Connectivity for Feedback Vertex Set

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