An $s$-club is a graph with whose diameter is at most $s$. Let $G$ be a graph. A set of vertices $D\subseteq V(G)$ is an $s$-club deleting (\textsc{$s$-CD}) set if each connected component of $G-D$ is an $s$-club. In the \textsc{$s$-Club Cluster Vertex Deletion ($s$-CVD)} problem, the goal is to find an $s$-CD set with minimum cardinality. When $s=1$, the \textsc{$s$-CVD} is equivalent to the well-studied \textsc{Cluster Vertex Deletion} problem. On the negative side, we show that Unless the Unique Games Conjecture is false, there is no $(2-\epsilon)-$algorithm for \textsc{$2$-CVD} on split graphs, for any $\epsilon > 0$. This contrasts the polynomial time solvability of \textsc{Cluster Vertex Deletion} on split graphs. We show that for each $s\geq 2$, $s$-CVD is NP-hard on bounded degree planar bipartite graphs and APX-hard on bounded degree bipartite graphs. On the positive side, we give a polynomial time algorithm to solve $s$-CVD on trapezoid graphs, for each $s\geq 1$.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_11