Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2206.00594 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910600126267392 |
|---|---|
| author | Bonamy, Marthe Bonnet, Édouard Déprés, Hugues Esperet, Louis Geniet, Colin Hilaire, Claire Thomassé, Stéphan Wesolek, Alexandra |
| author_facet | Bonamy, Marthe Bonnet, Édouard Déprés, Hugues Esperet, Louis Geniet, Colin Hilaire, Claire Thomassé, Stéphan Wesolek, Alexandra |
| contents | A graph is $\mathcal{O}_k$-free if it does not contain $k$ pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) $\mathcal{O}_k$-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of $\mathcal{O}_2$-free graphs without $K_{2,3}$ as a subgraph and whose treewidth is (at least) logarithmic.
Using our result, we show that Maximum Independent Set and 3-Coloring in $\mathcal{O}_k$-free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse $\mathcal{O}_k$-free graphs, and that deciding the $\mathcal{O}_k$-freeness of sparse graphs is polynomial time solvable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_00594 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sparse graphs with bounded induced cycle packing number have logarithmic treewidth Bonamy, Marthe Bonnet, Édouard Déprés, Hugues Esperet, Louis Geniet, Colin Hilaire, Claire Thomassé, Stéphan Wesolek, Alexandra Combinatorics Data Structures and Algorithms A graph is $\mathcal{O}_k$-free if it does not contain $k$ pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) $\mathcal{O}_k$-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of $\mathcal{O}_2$-free graphs without $K_{2,3}$ as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in $\mathcal{O}_k$-free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set, Minimum Vertex Cover, Minimum Dominating Set, Minimum Coloring) can be solved in polynomial time in sparse $\mathcal{O}_k$-free graphs, and that deciding the $\mathcal{O}_k$-freeness of sparse graphs is polynomial time solvable. |
| title | Sparse graphs with bounded induced cycle packing number have logarithmic treewidth |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2206.00594 |