Subexponential-time algorithms for finding large induced sparse subgraphs

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

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

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 graphs; feedback vertex set; subexponential algorithm; \(P_t\)-free graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C42: Density (toughness, etc.)