Chordal deletion is fixed-parameter tractable

DOI10.1007/s00453-008-9233-8zbMath1220.05066MaRDI QIDQ973007

Dániel Marx

Publication date: 28 May 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9233-8

zbMATH Keywords

chordal graphs; fixed-parameter tractability; chordal deletion

Mathematics Subject Classification ID

05C38: Paths and cycles

Related Items

Approximation and Kernelization for Chordal Vertex Deletion, Unnamed Item, Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Backdoor Sets for CSP., Modification to Planarity is Fixed Parameter Tractable, Paths to Trees and Cacti, Unnamed Item, Quadratic vertex kernel for split vertex deletion, Conflict free version of covering problems on graphs: classical and parameterized, Chordless Cycle Packing Is Fixed-Parameter Tractable, Unnamed Item, Vertex deletion into bipartite permutation graphs, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, Polynomial Kernel for Interval Vertex Deletion, A survey of parameterized algorithms and the complexity of edge modification, Chordal editing is fixed-parameter tractable, Satisfiability of acyclic and almost acyclic CNF formulas, Parameterized complexity of vertex deletion into perfect graph classes, Parameterized complexity of three edge contraction problems with degree constraints, Improved kernel results for some FPT problems based on simple observations, Unit interval editing is fixed-parameter tractable, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Parameterized complexity of finding connected induced subgraphs, Unit interval vertex deletion: fewer vertices are relevant, The critical node detection problem in networks: a survey, Proper interval vertex deletion, Paths to trees and cacti, Subexponential parameterized algorithms and kernelization on almost chordal graphs, A polynomial kernel for bipartite permutation vertex deletion, Towards constant-factor approximation for chordal/distance-hereditary vertex deletion, Vertex deletion into bipartite permutation graphs, Distance from triviality 2.0: hybrid parameterizations, Erdős-Pósa property of chordless cycles and its applications, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Modifying a graph using vertex elimination, Faster parameterized algorithms for deletion to split graphs, Obtaining a planar graph by vertex deletion, Contracting graphs to paths and trees, Parameterized complexity of Eulerian deletion problems, A faster FPT algorithm for bipartite contraction, Open Problems on Graph Coloring for Special Graph Classes, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs, Graph Minors and Parameterized Algorithm Design, Measuring Indifference: Unit Interval Vertex Deletion, Proper Interval Vertex Deletion, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Parameterized Complexity of Eulerian Deletion Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Parameterized coloring problems on chordal graphs
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• The node-deletion problem for hereditary properties is NP-complete
• Treewidth. Computations and approximations
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of vertex colouring
• Computing crossing numbers in quadratic time
• Graph minors. XIII: The disjoint paths problem
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Wheel-Free Deletion Is W[2-Hard]
• Obtaining a Planar Graph by Vertex Deletion
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Detecting a Network Failure
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• Complexity classification of some edge modification problems