2014/02/13 by Ivan Bliznets, Bliznets, Ivan, Fedor V. Fomin +5
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Parallel Computing and Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1402.3473
v2: An overview of the proof has been added; v3: updated introduction
arxiv created 2014/11/10 · arxiv updated 2014/11/11
In the Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into an interval graph, i.e., a graph admitting an intersection model of intervals on a line. Motivated by applications in sparse matrix multiplication and molecular biology, Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] asked for a fixed-parameter algorithm solving this problem. This question was answer affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k2kn3m). We give the first subexponential parameterized algorithm solving Interval Completion in time kO(√(k)) nO(1). This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.