Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm

DOI10.1137/21m140482xarXiv1907.04442OpenAlexW3135579236MaRDI QIDQ6115414

Dimitrios M. Thilikos, Julien Baste, Ignasi Sau

Publication date: 10 August 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingtreewidthparameterized complexitygraph minorsirrelevant vertexhitting minors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Irrelevant vertices for the planar disjoint paths problem
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Exact exponential algorithms.
• A new proof of the flat wall theorem
• The node-deletion problem for hereditary properties is NP-complete
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Rooted routing in the plane
• On the solution of linear recurrence equations
• Which problems have strongly exponential complexity?
• A faster parameterized algorithm for pseudoforest deletion
• Explicit linear kernels for packing problems
• Graph minors. XIII: The disjoint paths problem
• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• A lower bound on the tree-width of graphs with irrelevant vertices
• Deleting vertices to graphs of bounded genus
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The extremal function for noncomplete minors
• A tight lower bound for vertex planarization on graphs of bounded treewidth
• Hitting forbidden subgraphs in graphs of bounded treewidth
• On the vertex cover \(P_3\) problem parameterized by treewidth
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A shorter proof of the graph minor algorithm
• The Design of Approximation Algorithms
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• (Meta) Kernelization
• Explicit Linear Kernels via Dynamic Programming
• Bidimensionality and Kernels
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
• Representative Sets and Irrelevant Vertices
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
• A Near-Optimal Planarization Algorithm
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Slightly Superexponential Parameterized Problems
• The Parameterized Complexity of Graph Cyclability
• Encyclopedia of Algorithms
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions

This page was built for publication: Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm