{
  "id": "1510.02639",
  "version": "v1",
  "published": "2015-10-09T11:36:23.000Z",
  "updated": "2015-10-09T11:36:23.000Z",
  "title": "The Price of Connectivity for Feedback Vertex Set",
  "authors": [
    "Rémy Belmonte",
    "Pim van 't Hof",
    "Marcin Kamiński",
    "Daniël Paulusma"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 ${\\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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-10-09T11:36:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "connectivity",
      "free graph",
      "minimum feedback vertex set",
      "minimum connected feedback vertex set",
      "maximum ratio"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151002639B"
    }
  }
}