Improved Kernels for Edge Modification Problems.
2021
In an edge modification problem, we are asked to modify at most $k$ edges to a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them:
\begin{itemize}
\item a $2 k$-vertex kernel for the cluster edge deletion problem,
\item a $3 k^2$-vertex kernel for the trivially perfect completion problem,
\item a $5 k^{1.5}$-vertex kernel for the split completion problem and the split edge deletion problem, and
\item a $5 k^{1.5}$-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem.
\end{itemize}
Moreover, our kernels for split completion and pseudo-split completion have only $O(k^{2.5})$ edges. Our results also include a $2 k$-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI