On the parameterized complexity of s-club cluster deletion problems

We study the parameterized complexity of the s-CLUB CLUSTER EDGE DELETION (s-CLUB CLUSTER VERTEX DELETION) problem: Given a graph G and two integers s > 2 and k > 1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s-CLUB CLUSTER EDGE DELETION and s -CLUB CLUSTER VERTEX DELETION problems are known to be NP-hard already when s = 2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s-CLUB COVER, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d > 1 and s > 2.& COPY; 2023 Elsevier B.V. All rights reserved.