In the Proper 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 a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999], who showed an algorithm for the problem working in O(16~k • (n + m)) time. In this paper we present an algorithm with running time k~(O(k~(2/3))) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for Proper Interval Completion.
展开▼
