A SUBEXPONENTIAL PARAMETERIZED ALGORITHM FOR PROPER INTERVAL COMPLETION

作者：Bliznets Ivan^*; Fomin Fedor V; Pilipczuk Marcin; Pilipczuk Michal

来源：SIAM Journal on Discrete Mathematics, 2015, 29(4): 1961-1987.

DOI：10.1137/140988565

• fixed-parameter tractability
• proper interval graphs
• proper interval completion
• subexponential algorithm

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 [SIAM J. Comput., 28 (1999), pp. 1906-1922], 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(k2/3)) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for Proper Interval Completion.

• 出版日期2015