Hitting forbidden induced subgraphs on bounded treewidth graphs

DOI10.1016/j.ic.2021.104812OpenAlexW3211149322MaRDI QIDQ2051840

Ignasi Sau, Uéverton dos Santos Souza

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingtreewidthlower boundinduced subgraphsparameterized complexityexponential time hypothesishitting subgraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Streaming deletion problems parameterized by vertex cover ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Faster parameterized algorithms for minor containment
• The node-deletion problem for hereditary properties is NP-complete
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Linear-time algorithms for eliminating claws in graphs
• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• A tight lower bound for vertex planarization on graphs of bounded treewidth
• Hitting forbidden subgraphs in graphs of bounded treewidth
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Graph Theory
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• A Near-Optimal Planarization Algorithm
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Dynamic programming for graphs on surfaces
• Parameterized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Hitting forbidden induced subgraphs on bounded treewidth graphs