Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

Abstract

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.

30 pages, 6 figures. v5: revised version

References in corpus (3)

• Grid Induced Minor Theorem for Graphs of Small Degree
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Induced subgraphs and tree decompositions V. One neighbor in a hole

Cited by in corpus (4)

• Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors
• Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth
• Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
• Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets