Back to Search Start Over

Taming graphs with no large creatures and skinny ladders

Authors :
Gajarský, Jakub
Jaffke, Lars
Lima, Paloma T.
Novotná, Jana
Pilipczuk, Marcin
Rzążewski, Paweł
Souza, Uéverton S.
Publication Year :
2022

Abstract

We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ 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 \in \mathcal{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 $\mathcal{G}$. 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).

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2205.01191
Document Type :
Working Paper