摘要: 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-fr... 展开 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. 收起