The complexity of induced minors and related problems

DOI10.1007/BF01190507zbMath0816.68070MaRDI QIDQ1346772

Jan Kratochvíl, Michael R. Fellows, Frank Pfeiffer, Matthias Middendorf

Publication date: 19 July 1995

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

treewidthNP-completenessgraph minors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (31)

Algorithmic complexity of list colorings ⋮ Chordless paths through three vertices ⋮ Detecting induced star-like minors in polynomial time ⋮ Graph editing to a fixed target ⋮ Planar Embeddings with Small and Uniform Faces ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs ⋮ Detecting induced minors in AT-free graphs ⋮ Hypertree-depth and minors in hypergraphs ⋮ The Induced Disjoint Paths Problem ⋮ A linear time algorithm for the induced disjoint paths problem in planar graphs ⋮ On graph contractions and induced minors ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Algorithms for finding an induced cycle in planar graphs ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ MSOL restricted contractibility to planar graphs ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Contracting bipartite graphs to paths and cycles ⋮ Contracting bipartite graphs to paths and cycles ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Classes and recognition of curve contact graphs ⋮ Containment relations in split graphs ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Efficient approximation for restricted biclique cover problems ⋮ On a class of covering problems with variable capacities in wireless networks ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Satisfiability of co-nested formulas ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs without \(K_ 4\) and well-quasi-ordering
• A note on odd/even cycles
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• Disjoint homotopic paths and trees in a planar graph
• Induced matchings
• Induced circuits in planar graphs
• Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Noncrossing Subgraphs in Topological Layouts
• Universality considerations in VLSI circuits
• A Polynomial Solution to the Undirected Two Paths Problem
• Planar Formulae and Their Uses
• On the Computational Complexity of Combinatorial Problems
• A linear time algorithm for finding tree-decompositions of small treewidth
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: The complexity of induced minors and related problems