TY - JOUR

T1 - Tractability of parameterized completion problems on chordal and interval graphs

T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science

AU - Kaplan, Haim

AU - Shamir, Ron

AU - Tarjan, Robert E.

N1 - Funding Information:
Research supported in part by a grant from the Minstry of Science and the Arts, Israel. Research at Princeton University partially supported by NSF, Grant No. CCR-8920505 and the Office of Naval Research, Contract No. N00014-91-J-1463.
Funding Information:
*Department of Computer Science, Princeton University, Princeton, N J 08544 USA. hklQcs.princeton.edu. 'Department of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel-Aviv 69978 ISRAEL. Research supported in part by a grant from the Minstry of Science and the Arts, Israel. shamirOmath.tau.ac.il *Department of Computer Science, Princeton University, Princeton, NJ 08544 USA and NEC Institute, Princeton, NJ. Research at Princeton University partially sup ported by NSF, Grant No. CCR-8920505 and the Of- fice of Naval Research, Contract No. N00014-91-J-1463. retOcs.princeton.edu.
Publisher Copyright:
© 1994 IEEE

PY - 1994

Y1 - 1994

N2 - We study the parameterized complexity of several NP-Hard graph completion problems: The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k5mn + f(k)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). PROPER INTERVAL GRAPH COMPLETION problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)nk-1) algorithm, so it is polynomial for fixed k. on the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect.

AB - We study the parameterized complexity of several NP-Hard graph completion problems: The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k5mn + f(k)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). PROPER INTERVAL GRAPH COMPLETION problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)nk-1) algorithm, so it is polynomial for fixed k. on the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect.

UR - http://www.scopus.com/inward/record.url?scp=84968432358&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968432358&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1994.365715

DO - 10.1109/SFCS.1994.365715

M3 - Conference article

AN - SCOPUS:84968432358

SP - 780

EP - 791

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SN - 0272-5428

Y2 - 20 November 1994 through 22 November 1994

ER -