Interval Deletion is Fixed-Parameter Tractable

2012/11/26 by Yixin Cao, Dániel Marx, Cao, Yixin +1 · 2 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #semigroups and automata theory #DNA and Biological Computing

paper · pdf · doi:10.48550/arxiv.1211.5933

Abstract

We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10^k ⋅ n^O(1) for this problem, that is, we show the problem is fixed-parameter tractable.

Cited by

• A Finer View of the Parameterized Landscape of Labeled Graph Contractions
• Quadratic Kernel for Cliques or Trees Vertex Deletion

Related

• Unit Interval Editing is Fixed-Parameter Tractable
• A Polynomial kernel for Proper Interval Vertex Deletion
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Single Exponential FPT Algorithm for Interval Vertex Deletion and\n Interval Completion Problem
• Unit Interval Vertex Deletion: Fewer Vertices are Relevant