Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2024

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces

Abstract

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 G if and only if sup{$EP_H$(G) | G$ ∈ G$} is finite. We prove this conjecture for the class H of Kuratowski-connected shallow-vortex minors by showing that, for every non- planar H ∈ 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 $H$.
Fichier principal
Vignette du fichier
LIPIcs.ICALP.2024.114.pdf (1.31 Mo) Télécharger le fichier
Licence

Dates and versions

lirmm-04702132 , version 1 (19-09-2024)

Licence

Identifiers

Cite

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht. Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces. ICALP 2024 - 51st International Colloquium on Automata, Languages, and Programming, Jul 2024, Tallin, Estonia. pp.114:1-114:19, ⟨10.4230/LIPIcs.ICALP.2024.114⟩. ⟨lirmm-04702132⟩
7 View
6 Download

Altmetric

Share

More