2026-07-26T07:59:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15396 2024-03-06T10:55:39Z ddc:004 open_access

Improved Kernels for Edge Modification Problems Cao, Yixin Ke, Yuping Kernelization edge modification cluster trivially perfect graphs split graphs In an edge modification problem, we are asked to modify at most k edges of a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them: - a 2 k-vertex kernel for the cluster edge deletion problem, - a 3 k²-vertex kernel for the trivially perfect completion problem, - a 5 k^{1.5}-vertex kernel for the split completion problem and the split edge deletion problem, and - a 5 k^{1.5}-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem. Moreover, our kernels for split completion and pseudo-split completion have only O(k^{2.5}) edges. Our results also include a 2 k-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yixin Cao and Yuping Ke 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.13 urn:nbn:de:0030-drops-153965 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.13 eng https://creativecommons.org/licenses/by/4.0/legalcode