@inproceedings{7b0832ddddc1404e80b612b5e896936a,
title = "Polynomial Kernels for Paw-Free Edge Modification Problems",
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 -vertex kernels for them. This is part of an ongoing program that aims at understanding compressibility of H-free edge modification problems.",
keywords = "Graph modification, Kernelization, Paw-free graph",
author = "Yixin Cao and Yuping Ke and Hanchun Yuan",
note = "Funding Information: Supported by RGC grants 15201317 and 15226116, and NSFC grant 61972330. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020 ; Conference date: 18-10-2020 Through 20-10-2020",
year = "2020",
doi = "10.1007/978-3-030-59267-7_4",
language = "English",
isbn = "9783030592660",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "37--49",
editor = "Jianer Chen and Qilong Feng and Jinhui Xu",
booktitle = "Theory and Applications of Models of Computation - 16th International Conference, TAMC 2020, Proceedings",
address = "Germany",
}