Polynomial Kernels for Paw-free Edge Modification Problems
share
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.
READ FULL TEXT
