论文标题
线图删除的多项式内核
A Polynomial Kernel for Line Graph Deletion
论文作者
论文摘要
图$ g $的线图是$ l（g）$，其顶点集是$ g $的边缘集，如果$ e，f \ in E（g）$ in（g）$，则在$ g $中的endect a（g）$之间存在边缘。如果是某些图的界限图，则称为线图。我们研究线条环删除问题，该问题询问我们是否可以从输入图$ g $中删除最多$ k $的边缘，以使结果图是线图。更准确地说，我们给出了一个多项式内核，用于使用$ \ mathcal {o}（k^{5}）$ vertices。这回答了2013年FalkHüffner在内核（Worker）研讨会上提出的一个公开问题。
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.
