On the parameterized complexity of s-club cluster edge deletion

Abstract

We study the parameterized and kernelization complexity of the s-Club Cluster Edge Deletion problem, a natural distance-bounded generalization of Cluster Edge Deletion. Given a graph and integers , the goal is to delete at most k edges so that every connected component in the resulting graph has diameter at most s. This problem captures a broad class of distance-constrained graph modification problems that interpolate between clustering and connectivity control. On the structural side, we settle an open question of Montecchiani, Ortali, Piselli, and Tappini (Theoretical Computer Science, 2023) by proving that the problem is W[1]-hard when parameterized by pathwidth plus the maximum number of allowed s-clubs, and consequently also by treewidth plus the maximum number of allowed s-clubs, showing that the diameter bound s is indispensable for fixed-parameter tractability. In contrast, we identify several width and density parameters for which the dependence on s is unnecessary: the problem is fixed-parameter tractable when parameterized by treedepth, neighborhood diversity, or the cluster vertex deletion number. This generalizes previous FPT results known only for . We also complement these results by proving that no polynomial kernel exists when parameterized by the vertex cover number, even for . Finally, we present an FPT bicriteria approximation scheme that, for graphs excluding long induced cycles, runs in time and produces a solution of size at most k whose components have diameter at most . We also initiate the study of the directed variant, s-Club Cluster Arc Deletion, and show that it is W[1]-hard when parameterized by k, even on directed acyclic graphs.