2026-07-23T20:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16996 2024-03-06T10:58:55Z ddc:004 open_access

Taming Graphs with No Large Creatures and Skinny Ladders Gajarský, Jakub Jaffke, Lars Lima, Paloma T. Novotná, Jana Pilipczuk, Marcin Rzążewski, Paweł Souza, Uéverton S. Minimal separator hereditary graph class We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] 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 𝒢. 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Gajarský and Lars Jaffke and Paloma T. Lima and Jana Novotná and Marcin Pilipczuk and Paweł Rzążewski and Uéverton S. Souza 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.58 urn:nbn:de:0030-drops-169969 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.58 eng https://creativecommons.org/licenses/by/4.0/legalcode