๐ฎ
๐ฎ
The Ethereal
A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
May 24, 2024 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Martin Milaniฤ, Nevena Pivaฤ
arXiv ID
2405.15543
Category
math.CO: Combinatorics
Cross-listed
cs.DM,
cs.DS
Citations
2
Venue
arXiv.org
Last Checked
6 months ago
Abstract
A minimal separator in a graph is an inclusion-minimal set of vertices that separates some fixed pair of nonadjacent vertices. A graph class is said to be tame if there exists a polynomial upper bound for the number of minimal separators of every graph in the class, and feral if it contains arbitrarily large graphs with exponentially many minimal separators. Building on recent works of Gartland and Lokshtanov [SODA 2023] and Gajarskรฝ, Jaffke, Lima, Novotnรก, Pilipczuk, Rzฤ
ลผewski, and Souza [arXiv, 2022], we show that every graph class defined by a single forbidden induced minor or induced topological minor is either tame or feral, and classify the two cases. This leads to new graph classes in which Maximum Weight Independent Set and many other problems are solvable in polynomial time. We complement the classification results with polynomial-time recognition algorithms for the maximal tame graph classes appearing in the obtained classifications.
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