| Autor: |
Gajarský, Jakub, Jaffke, Lars, Lima, Paloma T., Novotná, Jana, Pilipczuk, Marcin, Rzążewski, Paweł, Souza, Uéverton S. |
| Rok vydání: |
2022 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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). |
| Databáze: |
arXiv |
| Externí odkaz: |
|
