Finding topological subgraphs is fixed-parameter tractable
From MaRDI portal
Publication:5419118
DOI10.1145/1993636.1993700zbMath1288.05058arXiv1011.1827OpenAlexW1965012931MaRDI QIDQ5419118
Dániel Marx, Paul Wollan, Ken-ichi Kawarabayashi, Martin Grohe
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.1827
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (52)
Systematic Refinement of Abstract State Machines with Higher-Order Logic ⋮ Planar Disjoint-Paths Completion ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ A Retrospective on (Meta) Kernelization ⋮ Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Mengerian temporal graphs revisited ⋮ A Basic Parameterized Complexity Primer ⋮ Graph Minors and Parameterized Algorithm Design ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Planar disjoint-paths completion ⋮ Graph editing to a fixed target ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Forbidding Kuratowski Graphs as Immersions ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Detecting induced minors in AT-free graphs ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Combing a Linkage in an Annulus ⋮ Mengerian graphs: characterization and recognition ⋮ Unnamed Item ⋮ Graphs of scramble number two ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Contracting planar graphs to contractions of triangulations ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Characterizing graphs of small carving-width ⋮ Confronting intractability via parameters ⋮ Graphs with no 7-wheel subdivision ⋮ Backdoor Sets for CSP. ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ On the complexity of the identifiable subgraph problem ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete ⋮ Unnamed Item ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ Induced disjoint paths in AT-free graphs ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ A Slice Theoretic Approach for Embedding Problems on Digraphs ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Containment relations in split graphs ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Parameterized complexity of set-restricted disjoint paths on chordal graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
This page was built for publication: Finding topological subgraphs is fixed-parameter tractable
