Open Problem 2: Does Claw-free Edge Deletion admit a polynomial kernel?
Status: Unresolved
Status: Unresolved
Claw-free Edge Deletion: Given a graph G and an integer k, find whether
there exist at most k edges in G such that deleting them from G results
in a graph without any induced claw graphs. (Parameter: k)
[1] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk. "Open problems in Workshop on Kernels" 2013.
[2] Yannakakis, Mihalis. "Edge-deletion problems." SIAM Journal on Computing 10, no. 2 (1981): 297-309.
- First raised in Worker 2013 [1].
- The problem is known to be NP-Complete even for bounded degree graphs [2].
- The hardness reduction in [2] implies that the problem cannot be solved in parameterized subexponential time.
- The problem is trivially in FPT (see [3]).
- The problem admits a polynomial kernel for bounded degree graphs [4]
[1] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk. "Open problems in Workshop on Kernels" 2013.
[2] Yannakakis, Mihalis. "Edge-deletion problems." SIAM Journal on Computing 10, no. 2 (1981): 297-309.
[3] Cai, Leizhen. "Fixed-parameter tractability of graph modification problems for hereditary properties." Information Processing Letters 58, no. 4 (1996): 171-176.
[4] Aravind, N. R., R. B. Sandeep, and Naveen Sivadasan. "On Polynomial Kernelization of -free Edge Deletion." Algorithmica 79, no. 3 (2017): 654-666.