Interval Completion Is Fixed Parameter Tractable

Abstract

We present an algorithm with runtime $O(k^{2k}n^3m)$ for the following NP-complete problem [M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979, problem GT35]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question [H. Kaplan, R. Shamir, and R. E. Tarjan, SIAM J. Comput., 28 (1999), pp. 1906–1922; R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999; M. Serna and D. Thilikos, Bull. Eur. Assoc. Theory Comput. Sci. EATCS, 86 (2005), pp. 41–65; G. Gutin, S. Szeider, and A. Yeo, in Proceedings IWPEC 2006, Lecture Notes in Comput. Sci. 4169, Springer-Verlag, Berlin, 2006, pp. 60–71], first posed by Kaplan, Shamir, and Tarjan, of whether this problem was fixed parameter tractable. The problem has applications in profile minimization for sparse matrix computations [J. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; R. E. Tarjan, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, 1976, pp. 3–22], and our results show tractability for the case of a small number k of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph and combines this with a greedy algorithm when graphs of a certain structure are reached by the search.