Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek · Society for Industrial and Applied Mathematics eBooks · 2023
A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in Ok-free graphs can be solved in quasi-polynomial time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. 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 Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable. * This work was supported by the ANR projects DISTANCIA (ANR-17-CE40-0015), DIGRAPHS (ANR-19-CE48-0013-01), and TWIN-WIDTH (ANR-21-CE48-0014-01), by the LabEx PERSYVAL-lab (ANR-11-LABX-0025), and by the Vanier Canada Graduate Scholarships program. † The full version of the paper can be accessed at https://arxiv.org/abs/2206.00594