2026-07-24T00:34:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9473 2024-03-06T10:43:50Z ddc:004 open_access

A Polynomial Kernel for Diamond-Free Editing Cao, Yixin Rai, Ashutosh Sandeep, R. B. Ye, Junjie Kernelization Diamond-free H-free editing Graph modification problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yixin Cao and Ashutosh Rai and R. B. Sandeep and Junjie Ye 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.10 urn:nbn:de:0030-drops-94732 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.10 eng https://creativecommons.org/licenses/by/3.0/legalcode