Chordal editing is fixed-parameter tractable

DOI10.1007/s00453-015-0014-xzbMath1344.68095arXiv1405.7859OpenAlexW2141235933MaRDI QIDQ300460

Yixin Cao, Dániel Marx

Publication date: 28 June 2016

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

holeschordal graphchordal completionchordal deletionclique tree decompositiongraph modification problemsparameterized computationsimplicial vertex sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Vertex deletion into bipartite permutation graphs ⋮ Structural parameterizations with modulator oblivion ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ A polynomial kernel for block graph deletion ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Solving problems on graphs of high rank-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Unit interval editing is fixed-parameter tractable ⋮ Paths to trees and cacti ⋮ Vertex deletion into bipartite permutation graphs ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Unnamed Item ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Vertex deletion problems on chordal graphs ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Vertex Deletion Problems on Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Unit interval editing is fixed-parameter tractable
• Finding odd cycle transversals.
• On rigid circuit graphs
• Parameterized coloring problems on chordal graphs
• Chordal deletion is fixed-parameter tractable
• Maximal chordal subgraphs
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Motivations and history of some of my conjectures
• Parameterized complexity of vertex colouring
• Triangulated graphs and the elimination process
• Finding small separators in linear time via treewidth reduction
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• On Feedback Vertex Set New Measure and New Structures
• Finding a Maximum Clique in an Arbitrary Graph
• Node-Deletion NP-Complete Problems
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• Complexity classification of some edge modification problems

This page was built for publication: Chordal editing is fixed-parameter tractable