2026-07-20T07:29:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5589 2024-03-06T10:36:37Z ddc:004 open_access

A Polynomial Kernel for Block Graph Deletion Kim, Eun Jung Kwon, O-joung block graph polynomial kernel single-exponential FPT algorithm In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i.e., a graph in which each block is a clique. In this paper, we obtain a kernel with O(k^{6}) vertices for the Block Graph Deletion problem. This is a first step to investigate polynomial kernels for deletion problems into non-trivial classes of graphs of bounded rank-width, but unbounded tree-width. Our result also implies that Chordal Vertex Deletion admits a polynomial-size kernel on diamond-free graphs. For the kernelization and its analysis, we introduce the notion of 'complete degree' of a vertex. We believe that the underlying idea can be potentially applied to other problems. We also prove that the Block Graph Deletion problem can be solved in time 10^{k} * n^{O(1)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eun Jung Kim and O-joung Kwon 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.270 urn:nbn:de:0030-drops-55893 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.270 eng https://creativecommons.org/licenses/by/3.0/legalcode