AI summaryⓘ
The authors study a generalization of a famous result called the Erdős–Pósa theorem, which connects the presence of many disjoint cycles in a graph to the ability to remove a small set of vertices to eliminate all cycles. They extend this idea to more complex structures called planar graph minors, showing that if a graph doesn't contain many separated copies of such minors, it can be simplified by removing neighborhoods of vertices. Their approach uses properties of "sparse" graphs to find many independent substructures, leading to insights about tree-width and efficient algorithms for finding large independent sets in these graphs. This work bridges combinatorial theory and algorithm design for special classes of graphs.
Erdős–Pósa theoremplanar graph minorsgraph minorsdisjoint subgraphsindependent setstree-widthsparse graphsalgorithmic graph theorygraph neighborhoodsprotrusions
Authors
Maria Chudnovsky, Amadeus Reinald, Stéphan Thomassé
Abstract
The Erdős--Pósa theorem asserts that every graph $G$ with no $k$ disjoint cycles contains a set $X$ of $f(k)$ vertices such that $G\setminus X$ has no cycle. Robertson and Seymour showed that this Erdős--Pósa property also holds for $H$-minor models of any planar graph $H$. Equivalently, if $G$ has no $k$ minor models of $H$ pairwise at distance at least 1 (i.e. disjoint), then one can remove $f(k,H)$ balls of radius 0 (i.e. vertices) to make the graph $H$-minor free. We show that this coarse graph theory point of view generalizes to distance at least 2 versus radius 1 balls, yielding the induced Erdős--Pósa property for planar minors. Namely, every graph $G$ which does not contain $k$ pairwise non-adjacent minor models of a planar graph $H$ (we say that $G$ is $kH$-free) can be made $H$-minor free by removing $f(k,H)$ neighborhoods. The proof relies on the fact that sparse $kH$-free graphs have linearly many independent large protrusions. The same method gives that sparse $kH$-free graphs can be made $H$-minor free by deleting $O(\log n)$ vertices (and thus have logarithmic tree-width). This gives a quasi-polynomial algorithm for the Maximum Independent Set problem for $kH$-free graphs.