A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911886185857024 |
|---|---|
| author | Milanič, Martin Pivač, Nevena |
| author_facet | Milanič, Martin Pivač, Nevena |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15543 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor Milanič, Martin Pivač, Nevena Combinatorics Discrete Mathematics Data Structures and Algorithms 05C69, 05C75 (Primary) 05C40, 05C30, 05C85, 68R10 (Secondary) 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. |
| title | A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C69, 05C75 (Primary) 05C40, 05C30, 05C85, 68R10 (Secondary) |
| url | https://arxiv.org/abs/2405.15543 |