Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time

DOI10.1145/3406325.3451034MaRDI QIDQ6087005zbMATH OpenFDO

Authors Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.11402

zbMATH Keywords

\(C_{>t}\)-free graphs\(P_t\)-free graphsfeedback vertex setindependent set

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: For an integer $t$, a graph $G$ is called {em{$C_{>t}$-free}} if $G$ does not contain any induced cycle on more than~$t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO${}_2$ statement~$phi$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O(lo{g}^{4}n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $phi$. The running time can be improved to $n^{O(lo{g}^{2}n)}$ assuming $G$ is $P_t$-free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {sc{Maximum Weight Independent Set}} problem on $P_t$-free graphs in two directions: by encompassing the more general setting of $C_{>t}$-free graphs, and by being applicable to a much wider variety of problems, such as {sc{Maximum Weight Induced Forest}} or {sc{Maximum Weight Induced Planar Graph}}.

Cited in

(22)

• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Grid induced minor theorem for graphs of small degree
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
• Colouring graphs of bounded diameter in the absence of small cycles
• Induced disjoint paths and connected subgraphs for H-free graphs
• Classifying subset feedback vertex set for H-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Treewidth versus clique number. II: Tree-independence number
• Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Classifying subset feedback vertex set for \(H\)-free graphs
• Induced subgraphs of bounded treewidth and the container method
• Maximum independent set when excluding an induced minor: K₁ + tK₂ and tC₃ C₄
• Odd cycle transversal on P₅-free graphs in polynomial time
• Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument
• Tree decompositions meet induced matchings: beyond max weight independent set
• Tree decompositions meet induced matchings: beyond max weight independent set
• Graphs with no long claws: an improved bound for the analog of the Gyárfás' path argument

This page was built for publication: Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087005)