2026-07-23T04:54:45Z https://drops.dagstuhl.de/oai

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

Polynomial Kernels for Strictly Chordal Edge Modification Problems Dumas, Maël Perez, Anthony Todinca, Ioan Parameterized complexity kernelization algorithms graph modification strictly chordal graphs We consider the Strictly Chordal Editing problem, where one is given an undirected graph G = (V,E) and a parameter k ∈ ℕ and seeks to edit (add or delete) at most k edges from G to obtain a strictly chordal graph. Problems Strictly Chordal Completion and Strictly Chordal Deletion are defined similarly, by only allowing edge additions for the former, and only edge deletions for the latter. Strictly chordal graphs are a generalization of 3-leaf power graphs and a subclass of 4-leaf power graphs. They can be defined, e.g., as dart and gem-free chordal graphs. We prove the NP-completeness for all three variants of the problem and provide an O(k³) vertex-kernel for the completion version and O(k⁴) vertex-kernels for the two others. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maël Dumas and Anthony Perez and Ioan Todinca 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.17 urn:nbn:de:0030-drops-154005 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.17 eng https://creativecommons.org/licenses/by/4.0/legalcode