A Polynomial Kernel for Line Graph Deletion

Abstract

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\in 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 $\mathcal{O}(k^5)$ vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013.

To be published in the Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020)