Variants of Cluster-Vertex-Deletion problem

Question

The Unweighted Cluster-Vertex-Deletion problem is the following:

Input: An undirected graph G = (V, E) and a nonnegative number k

Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all vertices in X from G results in a cluster graph (i. e., a graph where every connected component forms a complete graph)?

This problem is NP-Complete. More information can be found here: Fixed-Parameter Algorithms for Cluster Vertex Deletion where FPT algorithms are given for a more general problem. In particular, for a weighted version of d-Cluster-Vertex-Deletion where $d$ is a parameter that limitates the number of cliques to be generated, they developed three algorithms with running times: $O(2^k \cdot k^9 + nm), O(1.40^k \cdot k^{3d} + nm)$ and $O(1.84^{k+d} + nm)$.

I was wondering if it there is some known result for the case where $G \setminus X$ is a disjoint union of exactly 2 cliques, or the case where $G \setminus X$ is a disjoint union of p-defective cliques (cliques that misses at most p edges) in both cases (exactly two p-defective cliques or any number of p-defective cliques). I am specially interested in algorithmic results such as FPT or approximation algorithms developed for any of these variants.

I couldn't found anything but I suspect there is some results on this or maybe can be mapped from some other very well studied problem.

Thanks in advance

Edit: Adding to the useful answers, here is a paper that I've recently found and show NP-Hardness of the variant separating in exactly two cliques (but for a weighted case). Approximating clique and biclique problems

Answer 1

The following paper gives an FPT algorithm for another variant of the problem, where we have to delete $k$ vertices to make the graph the disjoint union of s-plexes. An s-plex is a graph where every vertex is adjacent to all but s-1 of the other vertices; 1-plexes are precisely the cliques.

Approximation and Tidying–-A Problem Kernel for $s$-Plex Cluster Vertex Deletion
René van Bevern and Hannes Moser and Rolf Niedermeier

http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/approximation-and-tidying.pdf

Answer 2

It seems to me that the case where G\X is a disjoint union of exactly two cliques has an FPT algorithm with runtime $O^*(3^k)$.

Here's what the algorithm would do.

1. If $k \leq 0$ then output YES if and only if G is a disjoint union of two cliques.
2. If the input graph contains an induced path on three vertices ($P_3$), then at least one of these three vertices need to be deleted to turn the graph into a cluster graph. Thus we branch in three ways depending on a choice of vertex, decreasing the parameter by 1 in each branch. Output the OR of the recursive calls.
3. If the graph is induced $P_3$-free, it is a cluster graph. If there is only 1 clique in this cluster graph: output NO. If there are two cliques in this cluster graph: output YES. If there are more than 2 cliques: sum the number of vertices in all but the two largest cliques. If this number is more than k, then output NO (all those vertices need to be deleted to reduce the number of cliques to 2, but we can't afford this). If the sum is at most k, output YES.

The approach generalizes to obtaining a cluster graph with exactly $\ell$ cliques for any value of $\ell$.