Interval Deletion Is Fixed-Parameter Tractable

DOI10.1145/2629595zbMath1398.68220arXiv1211.5933OpenAlexW2003744153MaRDI QIDQ4962179

Yixin Cao, Dániel Marx

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

asteroidal triplemodular decompositioncongenial hole

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (27)

Paths to Trees and Cacti ⋮ Faster FPT algorithms for deletion to pairs of graph classes ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Quick but odd growth of cacti ⋮ Erdös-Pósa Property of Obstructions to Interval Graphs ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Parameterized complexity of perfectly matched sets ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ 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 ⋮ Unnamed Item ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Paths to trees and cacti ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ Unnamed Item ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

This page was built for publication: Interval Deletion Is Fixed-Parameter Tractable