Taming Graphs with No Large Creatures and Skinny Ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Masaříková, Marcin Pilipczuk, Paweł Rzążewski, Uéverton S. Souza · SIAM Journal on Discrete Mathematics · 2024
Abstract. We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] minimal separators. By a result of Fomin, Todinca, and Villanger [ SIAM J. Comput., 44 (2015), pp. 54–87] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from [Formula: see text]. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).