2026-08-17T18:43:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20257 2024-07-02T07:52:54Z ddc:004 open_access

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces Paul, Christophe Protopapas, Evangelos Thilikos, Dimitrios M. Wiederrecht, Sebastian Erdős-Pósa property Erdős-Pósa pair Graph parameters Graph minors Universal obstruction Surface containment In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa 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ős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa 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ős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa 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 ℋ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christophe Paul and Evangelos Protopapas and Dimitrios M. Thilikos and Sebastian Wiederrecht 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.114 urn:nbn:de:0030-drops-202576 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.114 eng https://creativecommons.org/licenses/by/4.0/legalcode