{
  "id": "2406.16647",
  "version": "v1",
  "published": "2024-06-24T13:55:34.000Z",
  "updated": "2024-06-24T13:55:34.000Z",
  "title": "Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces",
  "authors": [
    "Christophe Paul",
    "Evangelos Protopapas",
    "Dimitrios M. Thilikos",
    "Sebastian Wiederrecht"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In 1986 Robertson and Seymour proved a generalization of the seminal result of Erd\\H{o}s and P\\'osa on the duality of packing and covering cycles: A graph has the Erd\\H{o}s-P\\'osa property for minors if and only if it is planar. In particular, for every non-planar graph $H$ they gave examples showing that the Erd\\H{o}s-P\\'osa property does not hold for $H.$ Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erd\\H{o}s-P\\'osa property for minors. Liu's proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erd\\H{o}s-P\\'osa property for minors. We conjecture that for every graph $H,$ there exists a unique (up to a suitable equivalence relation) graph parameter ${\\textsf{EP}}_H$ such that $H$ has the Erd\\H{o}s-P\\'osa property in a minor-closed graph class $\\mathcal{G}$ if and only if $\\sup\\{\\textsf{EP}_H(G) \\mid G\\in\\mathcal{G}\\}$ is finite. We prove this conjecture for the class $\\mathcal{H}$ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar $H\\in\\mathcal{H},$ the parameter ${\\sf EP}_H(G)$ is precisely the maximum order of a Robertson-Seymour counterexample to the Erd\\H{o}s-P\\'osa property of $H$ which can be found as a minor in $G.$ Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in $\\mathcal{H}.$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-24T13:55:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C83",
      "05C75",
      "05C10",
      "05C85",
      "68R10",
      "G.2.2"
    ],
    "keywords": [
      "erdős-pósa property",
      "delineating half-integrality",
      "robertson-seymour counterexample",
      "conjecture",
      "small number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}