Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs

We study the parameterized complexity of three NP-hard graph completion pro blems. The minimum fill-in problem asks if a graph can be triangulated by a dding at most k edges. We develop O(c(k)m) and O(k(2)mn + f(k)) algorithms for this problem on a graph with n vertices and m edges. Here f(k) is expon ential in k and the constants hidden by the big-O notation are small and do not depend on k. In particular, this implies that the problem is fixed-par ameter tractable (FPT). The proper interval graph completion problem, motivated by molecular biolog y, asks if a graph can be made proper interval by adding no more than k edg es. We show that the problem is FPT by providing a simple search-tree-based algorithm that solves it in O(c(k)m)-time. Similarly, we show that the par ameterized version of the strongly chordal graph completion problem is FPT by giving an O(c(k)m log n)-time algorithm for it. All of our algorithms can actually enumerate all possible k-completions wit hin the same time bounds.