Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth

DOI10.4230/LIPICS.IPEC.2017.4MaRDI QIDQ5111863zbMATH OpenFDO

Authors Julien Baste, Ignasi Sau, Dimitrios M. Thilikos

Publication date 27 May 2020

zbMATH Keywords

dynamic programmingtreewidthexponential time hypothesisgraph minorsparameterized complexitytopological minorshitting minors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Hitting minors on bounded treewidth graphs. I: General upper bounds
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Hitting minors on bounded treewidth graphs. III. Lower bounds
• A complexity dichotomy for hitting small planar minors parameterized by treewidth
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary

Cites work

• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• (Meta) kernelization
• A near-optimal planarization algorithm
• A tight lower bound for vertex planarization on graphs of bounded treewidth
• Bidimensionality and kernels
• Deleting vertices to bound path length
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Explicit linear kernels via dynamic programming
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Graph minors. X: Obstructions to tree-decomposition
• Hitting forbidden minors: approximation and kernelization
• Lower bounds based on the exponential time hypothesis
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The node-deletion problem for hereditary properties is NP-complete
• Which problems have strongly exponential complexity?

Cited in

(12)

• Compactors for parameterized counting problems
• Modification to Planarity is Fixed Parameter Tractable
• 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
• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Local tree-width, excluded minors, and approximation algorithms
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• A complexity dichotomy for hitting small planar minors parameterized by treewidth
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• A single-exponential FPT algorithm for the \(K _{4}\)-minor cover problem
• Hitting forbidden induced subgraphs on bounded treewidth graphs

This page was built for publication: Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111863)