Open Problem 4: Does Line Graph Edge Deletion admits an algorithm running in time O*(2k)?
Status: Unresolved
Line Graph 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 line graph. (Parameter: k)
[1] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk. "Open problems in Workshop on Kernels" 2013.
Status: Unresolved
Line Graph 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 line graph. (Parameter: k)
Background
- A trivial branching algorithm based on forbidden induced subgraphs has a running time O*(11k).
- First raised in Worker 2013 [1]. (the question was to significantly improve from O*(11k)).
- The problem is known to be NP-Complete [2].
- The reduction in [2] implies that there is no parameterized subexponential-time algorithm (an algorithm running in time O*(2o(k))) for the problem, assuming the ETH.
- The problem admits a polynomial kernel [3].
[2] Yannakakis, Mihalis. "Edge-deletion problems." SIAM Journal on Computing 10, no. 2 (1981): 297-309.
[3] Eduard Eiben, William Lochet. "A polynomial kernel for line graph deletion". To appear in the proceedings of ESA 2020.