Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

DOI10.1145/3583688OpenAlexW3001367190MaRDI QIDQ6075759

Giannos Stamoulis, Dimitrios M. Thilikos, Petr A. Golovach

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3583688

zbMATH Keywords

treewidthvertex deletion problemsirrelevant vertex techniquetopological minors

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irrelevant vertices for the planar disjoint paths problem
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Faster parameterized algorithms for minor containment
• Monadic second-order evaluations on tree-decomposable graphs
• Graph minors. XX: Wagner's conjecture
• Embeddings of graphs with no short noncontractible cycles
• Linearity of grid minors in treewidth with applications through bidimensionality
• Chordal deletion is fixed-parameter tractable
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The node-deletion problem for hereditary properties is NP-complete
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The complexity of induced minors and related problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Optimally cutting a surface into a disk
• Embedding grids in surfaces
• Graph minors. XIII: The disjoint paths problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Obtaining planarity by contracting few edges
• Contraction obstructions for treewidth
• Obtaining a planar graph by vertex deletion
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Multiple-Source Shortest Paths in Embedded Graphs
• Odd cycle packing
• Finding shortest non-trivial cycles in directed graphs on surfaces
• (Meta) Kernelization
• Easy problems for tree-decomposable graphs
• Bidimensionality and Kernels
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Contractibility and NP-completeness
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth
• Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
• Hitting topological minors is FPT
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• Mathematical Foundations of Computer Science 2004
• A Near-Optimal Planarization Algorithm
• Finding topological subgraphs is fixed-parameter tractable
• Parameterized Algorithms
• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
• The Parameterized Complexity of Graph Cyclability
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions

This page was built for publication: Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable