๐ฎ
๐ฎ
The Ethereal
Taming graphs with no large creatures and skinny ladders
May 02, 2022 ยท The Ethereal ยท ๐ Embedded Systems and Applications
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Jakub Gajarskรฝ, Lars Jaffke, Paloma T. Lima, Jana Novotnรก, Marcin Pilipczuk, Paweล Rzฤ
ลผewski, Uรฉverton S. Souza
arXiv ID
2205.01191
Category
math.CO: Combinatorics
Cross-listed
cs.DM,
cs.DS
Citations
5
Venue
Embedded Systems and Applications
Last Checked
6 months ago
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).
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal