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

DOI10.1145/3406325.3451034arXiv2007.11402MaRDI QIDQ6087005FDOQ6087005

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)

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}}.

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)

Cited In (16)

• Classifying subset feedback vertex set for \(H\)-free graphs
• Feedback vertex set and even cycle transversal for \(H\)-free graphs: finding large block graphs
• Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
• Treewidth versus clique number. II: Tree-independence number
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• Grid induced minor theorem for graphs of small degree
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Colouring graphs of bounded diameter in the absence of small cycles
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• 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
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Classifying subset feedback vertex set for \(H\)-free graphs
• Induced subgraphs of bounded treewidth and the container method

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)