Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs
From MaRDI portal
Publication:5089257
DOI10.4230/LIPIcs.MFCS.2020.82OpenAlexW3082759585MaRDI QIDQ5089257
Uéverton dos Santos Souza, Ignasi Sau
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.82
dynamic programmingtreewidthlower boundinduced subgraphsparameterized complexityexponential time hypothesishitting subgraphs
Related Items (2)
\(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
Cites Work
- 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
- 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
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- 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
