View PDF HTML (experimental)

Abstract:We study the parameterized and kernelization complexity of the \emph{\textsc{$s$-Club Cluster Edge Deletion}} problem, a distance-bounded generalization of \emph{\textsc{Cluster Edge Deletion}}. Given a graph $G=(V,E)$ and integers $k,s$, the goal is to delete at most $k$ edges so that every resulting connected component has diameter at most $s$.
On the structural side, we settle an open question of Montecchiani, Ortali, Piselli, and Tappini (\emph{Theoretical Computer Science}, 2023) by proving W[1]-hardness parameterized by pathwidth plus the maximum number of allowed $s$-clubs, and consequently by treewidth plus this parameter. Thus, the diameter bound $s$ is inecessary for tractability under these parameters. In contrast, we show that dependence on \(s\) is unnecessary for several structural parameters: the problem is fixed-parameter tractable when parameterized by treedepth, neighborhood diversity, or cluster vertex deletion number, generalizing known results for $s=1.$
We further prove that no polynomial kernel exists when parameterized by vertex cover, even for $s=2$. On the positive side, we present an FPT bicriteria approximation scheme for graphs excluding long induced cycles, running in time $f(k,1/\epsilon)\cdot n^{\mathcal{O}(1)}$ and producing a solution of size at most $k$ whose components have diameter at most $(1+\epsilon)s$.
Finally, we initiate the study of the directed variant, \textsc{$s$-Club Cluster Arc Deletion}, and prove that it is W[1]-hard parameterized by $k$, even on directed acyclic graphs.

Submission history

From: Ajinkya Gaikwad [view email]
[v1] Wed, 8 Oct 2025 14:30:42 UTC (140 KB)
[v2] Fri, 17 Oct 2025 07:29:36 UTC (141 KB)
[v3] Thu, 30 Oct 2025 06:14:49 UTC (133 KB)
[v4] Mon, 3 Nov 2025 15:29:33 UTC (143 KB)
[v5] Sun, 30 Aug 2026 12:15:35 UTC (75 KB)