Detecting fixed patterns in chordal graphs in polynomial time

DOI10.1007/s00453-013-9748-5zbMath1291.68173OpenAlexW2003458989MaRDI QIDQ2249737

Pim van 't Hof, Daniël Paulusma, Pinar Heggernes, Rémy Belmonte, Marcin Kaminski, Petr A. Golovach

Publication date: 3 July 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/10684/1/10684.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Induced disjoint paths in circular-arc graphs in linear time, Graph editing to a fixed target, Mim-width. I. Induced path problems, On strictly chordality-\(k\) graphs, Detecting induced minors in AT-free graphs, The complexity of contracting bipartite graphs into small cycles, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Cops and robber on oriented graphs with respect to push operation, Unnamed Item, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Few induced disjoint paths for \(H\)-free graphs, Induced Disjoint Paths in Claw-Free Graphs, Contracting bipartite graphs to paths and cycles, Contracting bipartite graphs to paths and cycles, Induced disjoint paths in AT-free graphs, Parameterized complexity of set-restricted disjoint paths on chordal graphs, Few induced disjoint paths for \(H\)-free graphs

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graph contractions and induced minors
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Containment relations in split graphs
• On rigid circuit graphs
• Partitioning graphs into connected parts
• On the complexity of testing for odd holes and induced odd paths
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth. Computations and approximations
• The complexity of induced minors and related problems
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• The \(k\)-in-a-path problem for claw-free graphs
• Parametrized complexity theory.
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Edge Contractions in Subclasses of Chordal Graphs
• Contracting a Chordal Graph to a Split Graph or a Tree
• Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contractibility and NP-completeness
• Graph Classes: A Survey
• Finding topological subgraphs is fixed-parameter tractable
• Detecting induced subgraphs