Maël Dumas ; Anthony Perez ; Mathis Rocton ; Ioan Todinca - Polynomial kernels for edge modification problems towards block and strictly chordal graphs

dmtcs:12998 - Discrete Mathematics & Theoretical Computer Science, May 1, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.12998
Polynomial kernels for edge modification problems towards block and strictly chordal graphsArticle

Authors: Maël Dumas ; Anthony Perez ; Mathis Rocton ; Ioan Todinca

    We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph $G = (V,E)$ and an integer $k \in \mathbb{N}$ and seeks to edit (add or delete) at most $k$ edges from $G$ to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide $O(k^2)$ vertex-kernels for Block Graph Editing and Block Graph Deletion, $O(k^3)$ vertex-kernels for Strictly Chordal Completion and Strictly Chordal Deletion and a $O(k^4)$ vertex-kernel for Strictly Chordal Editing.


    Volume: vol. 27:2
    Section: Discrete Algorithms
    Published on: May 1, 2025
    Accepted on: February 14, 2025
    Submitted on: February 5, 2024
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 65 times.
    This article's PDF has been downloaded 30 times.