UP - logo
University of Primorska University Library (UPUK)
  • Sparse graphs with bounded induced cycle packing number have logarithmic treewidth [Elektronski vir]
    Bonamy, Marthe ...
    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.
    Source: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms [Elektronski vir] (Str. 3006-3028)
    Type of material - conference contribution
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 176719107

    Link(s):

    https://doi.org/10.1137/1.9781611977554.ch116
    https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch116
    DOI

Shelf entry