# Variants of Cluster-Vertex-Deletion problem

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.

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

• Have you tried to use the general NP-completeness result for hereditary graph properties by Lewis and Yannakakis, which is cited in the paper you mentioned? At least the “any number of p-defective cliques” version of your question should be answered by the result by Lewis and Yannakakis. – Tsuyoshi Ito Nov 22 '11 at 21:08
• @TsuyoshiIto: Thanks, I have seen it. Even I didn't proved it, I had supposed this variant is harder than the original Cluster-Vertex-Deletion, but maybe there is some known FPT algorithm developed or some deeper work over the problem. – user2582 Nov 22 '11 at 21:36
• Just to be clear, there is no indication in your question that you are interested in fixed parameter tractability of any of the problems. If that is the case, you should edit the question. – Tsuyoshi Ito Nov 22 '11 at 21:39

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

• Great! I was looking for something like this. – user2582 Nov 24 '11 at 20:28

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$.

• In step 3, I think that you meant to write “sum the number of vertices in all but the two largest cliques.” – Tsuyoshi Ito Nov 23 '11 at 14:47
• You're right of course. Just fixed it. – Bart Jansen Nov 23 '11 at 15:55
• Thanks, it was an easy and short algorithm. Algorithms from the paper referenced in the original question also solves this variant with a better upper bound. However I suspect that for this particular cases (except case of more than two p-defective cliques) can be solved faster, maybe even in polynomial time. – user2582 Nov 23 '11 at 16:36
• @user2582: You should make clear what you know and what you want to know in the question. “Thanks, but I know a better algorithm” is not a particularly polite response. – Tsuyoshi Ito Nov 23 '11 at 19:01
• @TsuyoshiIto: I was not intended to be unpolite. I apologize if it sounds that way. I thought it was clear that I was looking for research done on these specific variations of the problem. Saying that the problem of separating in K cliques (studied in the referenced paper) also covers the case when K=2 seems to be unnecessary. However seeing a simple and short algorithm that solves the problem is always useful and I appreciate that answer, thats why I said thanks, even it was not the specific answer I was looking for. – user2582 Nov 23 '11 at 19:43