2026-07-20T11:57:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20580 2024-08-23T05:50:28Z ddc:004 open_access

Breaking a Graph into Connected Components with Small Dominating Sets Bentert, Matthias Fellows, Michael R. Golovach, Petr A. Rosamond, Frances A. Saurabh, Saket Parameterized Algorithms Recursive Understanding Polynomial Kernels Degeneracy We study DOMINATED CLUSTER DELETION. Therein, we are given an undirected graph G = (V,E) and integers k and d and the task is to find a set of at most k vertices such that removing these vertices results in a graph in which each connected component has a dominating set of size at most d. We also consider the special case where d is a constant. We show an almost complete tetrachotomy in terms of para-NP-hardness, containment in XP, containment in FPT, and admitting a polynomial kernel with respect to parameterizations that are a combination of k,d,c, and Δ, where c and Δ are the degeneracy and the maximum degree of the input graph, respectively. As a main contribution, we show that the problem can be solved in f(k,d) ⋅ n^O(d) time, that is, the problem is FPT when parameterized by k when d is a constant. This answers an open problem asked in a recent Dagstuhl seminar (23331). For the special case d = 1, we provide an algorithm with running time 2^𝒪(klog k) nm. Furthermore, we show that even for d = 1, the problem does not admit a polynomial kernel with respect to k + c. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Michael R. Fellows and Petr A. Golovach and Frances A. Rosamond and Saket Saurabh 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.24 urn:nbn:de:0030-drops-205801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.24 eng https://creativecommons.org/licenses/by/4.0/legalcode