@inproceedings{dff663672dec4e229806dc771b1922d6,

title = "A polynomial kernel for diamond-free editing",

abstract = "Given a fixed graph H, the H-free editing problem asks whether we can edit at most k edges to make a graph contain no induced copy of H. We obtain a polynomial kernel for this problem when H is a diamond. The incompressibility dichotomy for H being a 3-connected graph and the classical complexity dichotomy suggest that except for H being a complete/empty graph, H-free editing problems admit polynomial kernels only for a few small graphs H. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of H-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.",

keywords = "Diamond-free, Graph modification problem, H-free editing, Kernelization",

author = "Yixin Cao and Ashutosh Rai and Sandeep, {R. B.} and Junjie Ye",

year = "2018",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.ESA.2018.10",

language = "English",

isbn = "9783959770811",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Hannah Bast and Grzegorz Herman and Yossi Azar",

booktitle = "26th European Symposium on Algorithms, ESA 2018",

address = "Germany",

note = "26th European Symposium on Algorithms, ESA 2018 ; Conference date: 20-08-2018 Through 22-08-2018",

}