A Polynomial Kernel for Line Graph Deletion

06/28/2020
by   Eduard Eiben, et al.
0

The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some graph. We study the Line-Graph-Edge Deletion problem, which asks whether we can delete at most k edges from the input graph G such that the resulting graph is a line graph. More precisely, we give a polynomial kernel for Line-Graph-Edge Deletion with 𝒪(k^5) vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset