Subexponential-time algorithms for finding large induced sparse subgraphs

DOI10.1007/s00453-020-00745-zzbMath1469.05159arXiv1910.01082OpenAlexW3046548273MaRDI QIDQ2041989

Karolina Okrasa, Michał Pilipczuk, Erik Jan van Leeuwen, Jana Novotná, Bartosz Walczak, Paweł Rzążewski

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

string graphsfeedback vertex setsubexponential algorithm\(P_t\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items (2)

Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Largest chordal and interval subgraphs faster than \(2^n\)
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs requiring exponential representations
• The node-deletion problem for hereditary properties is NP-complete
• Embeddings of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• Cycles of even length in graphs
• Treewidth of graphs with balanced separations
• Deleting vertices to graphs of bounded genus
• Das Geschlecht des vollständigen paaren Graphen
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Hitting forbidden subgraphs in graphs of bounded treewidth
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Large Induced Subgraphs via Triangulations and CMSO
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Exact Algorithm for the Maximum Induced Planar Subgraph Problem
• Separators in region intersection graphs
• Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
• Tight Running Time Lower Bounds for Vertex Deletion Problems
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Exact Algorithms via Monotone Local Search
• Parameterized Algorithms
• On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Optimality program in segment and string graphs

This page was built for publication: Subexponential-time algorithms for finding large induced sparse subgraphs