Open Problem 3: Is Perfect Completion fixed parameter tractable?
Status: Unresolved
Perfect Completion: Given a graph G and an integer k, find whether there exist at most k nonedges in G such that adding them in G results in a perfect graph. (Parameter: k)
[2] Natanzon, Assaf, Ron Shamir, and Roded Sharan. "Complexity classification of some edge modification problems." Discrete Applied Mathematics 113, no. 1 (2001): 109-128.
Status: Unresolved
Perfect Completion: Given a graph G and an integer k, find whether there exist at most k nonedges in G such that adding them in G results in a perfect graph. (Parameter: k)
Background
- First raised in 2014 [1].
- The problem is known to be NP-Complete [2].
[1] Bodlaender, Hans L., Pinar Heggernes, and Daniel Lokshtanov. "Graph modification problems (Dagstuhl seminar 14071)." In Dagstuhl Reports, vol. 4, no. 2. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.
[2] Natanzon, Assaf, Ron Shamir, and Roded Sharan. "Complexity classification of some edge modification problems." Discrete Applied Mathematics 113, no. 1 (2001): 109-128.