Résumé
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$.