Breaking a Graph into Connected Components with Small Dominating Sets

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.

Authors

• Matthias Bentert
• Michael R. Fellows
• Petr A. Golovach
• Frances A. Rosamond
• Saket Saurabh 0001

Keywords

• Parameterized Algorithms
• Recursive Understanding
• Polynomial Kernels
• Degeneracy