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

independent setfeedback vertex set\(P_t\)-free graphs\(C_{>t}\)-free graphs

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

(16)

• Feedback vertex set and even cycle transversal for \(H\)-free graphs: finding large block graphs
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Induced subgraphs of bounded treewidth and the container method
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
• Treewidth versus clique number. II: Tree-independence number
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Grid induced minor theorem for graphs of small degree
• Colouring graphs of bounded diameter in the absence of small cycles
• Classifying subset feedback vertex set for \(H\)-free graphs
• Classifying subset feedback vertex set for \(H\)-free graphs
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes

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)