Polynomial Kernels for Paw-free Edge Modification Problems

DOI10.1016/J.TCS.2021.08.015zbMATH Open1514.68232arXiv2003.11273MaRDI QIDQ6337384FDOQ6337384

Authors: Hanchun Yuan, Yuping Ke, Yixin Cao 

Publication date: 25 March 2020

Abstract: Let $H$ be a fixed graph. Given a graph $G$ and an integer $k$, the $H$-free edge modification problem asks whether it is possible to modify at most $k$ edges in $G$ to make it $H$-free. Sandeep and Sivadasan (IPEC 2015) asks whether the paw-free completion problem and the paw-free edge deletion problem admit polynomial kernels. We answer both questions affirmatively by presenting, respectively, $O(k)$-vertex and $O(k^4)$-vertex kernels for them. This is part of an ongoing program that aims at understanding compressibility of $H$-free edge modification problems.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

This page was built for publication: Polynomial Kernels for Paw-free Edge Modification Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337384)