A Subexponential Parameterized Algorithm for Proper Interval Completion
- 1 January 2015
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 29 (4) , 1961-1987
Abstract
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 $\mathcal{O}(16^k\cdot (n+m))$ time. In this paper we present an algorithm with running time $k^{\mathcal{O}(k^{2/3})} + \mathcal{O}(nm(kn+m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- An effective branching strategy based on structural relationship among multiple forbidden induced subgraphsJournal of Combinatorial Optimization, 2014
- Faster Parameterized Algorithms for Deletion to Split GraphsAlgorithmica, 2013
- Polynomial kernels for Proper Interval Completion and related problemsInformation and Computation, 2013
- Two edge modification problems without polynomial kernelsDiscrete Optimization, 2013
- Subexponential Parameterized Algorithm for Minimum Fill-InSIAM Journal on Computing, 2013
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphsJournal of the ACM, 2005
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval GraphsSIAM Journal on Computing, 1999
- Fixed-parameter tractability of graph modification problems for hereditary propertiesInformation Processing Letters, 1996
- Four Strikes Against Physical Mapping of DNAJournal of Computational Biology, 1995