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

Haim Kaplan, Ron Shamir, Robert E. Tarjan

Research output: Contribution to journalArticle

103 Scopus citations

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(ckm) and O(k2mn + 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(ckm)-time. Similarly, we show that the parameterized version of the strongly chordal graph completion problem is FPT by giving an O(ckm log n)-time algorithm for it. All of our algorithms can actually enumerate all possible k-completions within the same time bounds.

Original languageEnglish (US)
Pages (from-to)1906-1922
Number of pages17
JournalSIAM Journal on Computing
Volume28
Issue number5
DOIs
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs'. Together they form a unique fingerprint.

  • Cite this