## Abstract

We study the parameterized complexity of three NP-hard graph completion problems. The minimum fill-in problem asks if a graph can be triangulated by adding at most k edges. We developed 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 exponential 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-parameter tractable (FPT). The proper interval graph completion problem, motivated by molecular biology, asks if a graph can be made proper interval by adding no more than k edges. 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 parameterized 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 within the same time bounds.

Original language | English (US) |
---|---|

Pages (from-to) | 1906-1922 |

Number of pages | 17 |

Journal | SIAM Journal on Computing |

Volume | 28 |

Issue number | 5 |

DOIs | |

State | Published - 1999 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics