2024/07/12 by Christophe Paul, Paul, Christophe, Evangelos Protopapas +5
Mathematics · #Advanced Algebra and Geometry #Mathematical Analysis and Transform Methods #Holomorphic and Operator Theory
paper · pdf · doi:10.48550/arxiv.2407.09671
Let \cal G and \cal H be minor-closed graph classes. The pair (\cal H,\cal G) is an Erdős-Pósa pair (EP-pair) if there is a function f where, for every k and every G∈\cal G, either G has k pairwise vertex-disjoint subgraphs not belonging to \cal H, or there is a set S⊆ V(G) where |S|≤ f(k) and G-S∈\cal H. The classic result of Erdős and Pósa says that if F is the class of forests, then (\cal F,\cal G) is an EP-pair for every \cal G. The class \cal G is an EP-counterexample for \cal H if \cal G is minimal with the property that (\cal H,\cal G) is not an EP-pair. We prove that for every \cal H the set \mathfrakC\cal H of all EP-counterexamples for \cal H is finite. In particular, we provide a complete characterization of \mathfrakC\cal H for every \cal H and give a constructive upper bound on its size. Each class \cal G∈ \mathfrakC\cal H can be described as all minors of a sequence of grid-like graphs ⟨ \mathscrWk ⟩k∈ ℕ. Moreover, each \mathscrWk admits a half-integral packing: k copies of some H\not∈\cal H where no vertex is used more than twice. This gives a complete delineation of the half-integrality threshold of the Erdős-Pósa property for minors and yields a constructive proof of Thomas' conjecture on the half-integral Erdős-Pósa property for minors (recently confirmed, non-constructively, by Liu). Let h be the maximum size of a graph in \cal H. For every class \cal H, we construct an algorithm that, given a graph G and a k, either outputs a half-integral packing of k copies of some H \not∈ \cal H or outputs a set of at most 2^k\cal Oh(1) vertices whose deletion creates a graph in \cal H in time 2^2^k^\cal Oh(1)⋅ |G|4log |G|.