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

DOI10.1145/3406325.3451034arXiv2007.11402MaRDI QIDQ6087005

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

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)

Related Items (12)

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ 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 ⋮ 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 ⋮ Grid induced minor theorem for graphs of small degree ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Colouring graphs of bounded diameter in the absence of small cycles

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