Open Problem 1: Does Interval Completion admit a polynomial kernel?
Status: Unresolved
Interval 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 an interval graph. (Parameter: k)
Status: Unresolved
Interval 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 an interval graph. (Parameter: k)
Background
[1] Villanger, Yngve, Pinar Heggernes, Christophe Paul, and Jan Arne Telle. "Interval completion is fixed parameter tractable." SIAM Journal on Computing 38, no. 5 (2009): 2007-2020.
[2] Garey, Michael R., and David S. Johnson. Computers and intractability. Vol. 174. San Francisco: freeman, 1979.
- First raised in 2009 [1].
- The problem is proved to be NP-Complete in 1977 by Garey, Garvil, and Johnson (see GT35 in [2]).
- The problem is FPT [1].
- Assuming the ETH, the problem does not admit an algorithm with running time 2O(k1/4/logcn)nO(1) [3]
[1] Villanger, Yngve, Pinar Heggernes, Christophe Paul, and Jan Arne Telle. "Interval completion is fixed parameter tractable." SIAM Journal on Computing 38, no. 5 (2009): 2007-2020.
[2] Garey, Michael R., and David S. Johnson. Computers and intractability. Vol. 174. San Francisco: freeman, 1979.
[3] Bliznets, Ivan, Marek Cygan, Paweł
Komosa, Michał Pilipczuk, and Lukáš Mach. "Lower Bounds for the
Parameterized Complexity of Minimum Fill-in and Other Completion
Problems." ACM Transactions on Algorithms (TALG) 16, no. 2 (2020): 1-31.