<p>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.</p>

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

<p><a href="http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/approximation-and-tidying.pdf" rel="nofollow">http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/approximation-and-tidying.pdf</a></p>

CC BY-SA 3.0
2011-11-24T20:28:58.233Z
Great! I was looking for something like this.
user2582
CC BY-SA 3.0
2011-11-24T08:56:10.563Z
2011-11-24T08:56:10.563Z
Daniel Marx
<p>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)$.</p>

<p>Here's what the algorithm would do. </p>

<ol>
<li>If $k \leq 0$ then output YES if and only if G is a disjoint union of two cliques.</li>
<li>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.</li>
<li>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.</li>
</ol>

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

CC BY-SA 3.0
2011-11-23T14:47:26.680Z
In step 3, I think that you meant to write “sum the number of vertices in all but the two _largest_ cliques.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-23T15:55:26.647Z
You're right of course. Just fixed it.
Bart Jansen
CC BY-SA 3.0
2011-11-23T16:36:18.157Z
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
CC BY-SA 3.0
2011-11-23T19:01:51.633Z
@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
CC BY-SA 3.0
2011-11-23T19:43:52.953Z
@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
CC BY-SA 3.0
2011-11-24T00:11:06.553Z
@user2582: So do you mean that one should first read the paper which you cited to distinguish what you want to know from what you already know?  It is fine, but that is a lot of burden to answerers, and I do not know who wants to do that.  (I confess that I still have trouble locating where in the paper the “exactly K cliques” version is stated as you claimed.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-24T04:13:21.660Z
@TsuyoshiIto: No, I didn't expect that from readers. I just asked for some known results of some variants of a specific problem (Vertex-Cluster-Deletion) which was studied in the referenced paper. The case for two cliques is a particular case from the problem I described, because a cluster graph can have more or less than two cliques. I would try to edit question to let things more clear. Anyway, this discussion is pointless, if you think my question didn't follow the rules just report it to right people.
user2582
CC BY-SA 3.0
2011-11-24T04:27:19.093Z
@user2582: I just wanted to decide whether I should think further about your question or not.  Now I decided not to bother.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-24T04:52:13.277Z
@TsuyoshiIto: Sorry for making you lose time.
user2582
CC BY-SA 3.0
2011-11-23T10:37:51.743Z
2011-11-23T15:55:17.473Z
2011-11-23T15:55:17.473Z
Bart Jansen
<p>The Unweighted Cluster-Vertex-Deletion problem is the following:</p>

<p><strong>Input:</strong> An undirected graph G = (V, E) and a nonnegative number k</p>

<p><strong>Output:</strong> 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)?</p>

<p>This problem is NP-Complete.
More information can be found here:
<a href="http://www.google.com.ar/url?sa=t&amp;rct=j&amp;q=fixed%20parameter%20cluster%20vertex%20deletion&amp;source=web&amp;cd=1&amp;ved=0CCQQFjAA&amp;url=http%3A%2F%2Ftheinf1.informatik.uni-jena.de%2F~moser%2Fcluster-vertex-deletion-tocs08.pdf&amp;ei=3QnMTsztL47fgQeTkYSsDQ&amp;usg=AFQjCNEUO2ghJgyCdzRyR-IG-LtDYd4HEg&amp;sig2=jNM4G68kku33OP3boCv3rA" rel="nofollow">Fixed-Parameter Algorithms for Cluster Vertex Deletion</a> 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)$.</p>

<p>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 <em>p-defective</em> cliques (cliques that misses at most p edges) in both cases (exactly two <em>p-defective</em> cliques or any number of <em>p-defective</em> cliques). I am specially interested in algorithmic results such as FPT or approximation algorithms developed for any of these variants. </p>

<p>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.</p>

<p>Thanks in advance</p>

<p><strong>Edit:</strong>
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). 
<a href="http://www.google.com.ar/url?sa=t&amp;rct=j&amp;q=approximating%20clique%20and%20biclique%20problems&amp;source=web&amp;cd=1&amp;sqi=2&amp;ved=0CCQQFjAA&amp;url=http%3A%2F%2Friot.ieor.berkeley.edu%2F~dorit%2Fpub%2Fbiclique.ps&amp;ei=rsjPTtW9Nefz0gH78fmVCg&amp;usg=AFQjCNEzvt0bJ-RNKDLPNLQF4blDqtDcCA&amp;sig2=Oy4aWaHJAwPTXJsl2sP4sg" rel="nofollow">Approximating clique and biclique problems</a></p>

CC BY-SA 3.0
2011-11-22T21:08:33.243Z
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
CC BY-SA 3.0
2011-11-22T21:36:16.833Z
@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
CC BY-SA 3.0
2011-11-22T21:39:37.880Z
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
<ds.algorithms><graph-theory><graph-algorithms><fixed-parameter-tractable>
Variants of Cluster-Vertex-Deletion problem
user2582
# Variants of Cluster-Vertex-Deletion problem

(Asked by: username_0 on 2011-11-22)

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](http://www.google.com.ar/url?sa=t&rct=j&q=fixed%20parameter%20cluster%20vertex%20deletion&source=web&cd=1&ved=0CCQQFjAA&url=http%3A%2F%2Ftheinf1.informatik.uni-jena.de%2F~moser%2Fcluster-vertex-deletion-tocs08.pdf&ei=3QnMTsztL47fgQeTkYSsDQ&usg=AFQjCNEUO2ghJgyCdzRyR-IG-LtDYd4HEg&sig2=jNM4G68kku33OP3boCv3rA) 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](http://www.google.com.ar/url?sa=t&rct=j&q=approximating%20clique%20and%20biclique%20problems&source=web&cd=1&sqi=2&ved=0CCQQFjAA&url=http%3A%2F%2Friot.ieor.berkeley.edu%2F~dorit%2Fpub%2Fbiclique.ps&ei=rsjPTtW9Nefz0gH78fmVCg&usg=AFQjCNEzvt0bJ-RNKDLPNLQF4blDqtDcCA&sig2=Oy4aWaHJAwPTXJsl2sP4sg)

**Tags:** ds.algorithms, graph-theory, graph-algorithms, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-11-24. Score: 4 | Accepted answer

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>

> **Comments:**
> **username_0**: Great! I was looking for something like this.  

---

### Answer by username_3 on 2011-11-23. Score: 6

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

> **Comments:**
> **username_1**: In step 3, I think that you meant to write “sum the number of vertices in all but the two _largest_ cliques.”  
> **username_3**: You're right of course. Just fixed it.  
> **username_0**: 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.  
> **username_1**: @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.  
> **username_0**: @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.  
> **username_1**: @user2582: So do you mean that one should first read the paper which you cited to distinguish what you want to know from what you already know?  It is fine, but that is a lot of burden to answerers, and I do not know who wants to do that.  (I confess that I still have trouble locating where in the paper the “exactly K cliques” version is stated as you claimed.)  
> **username_0**: @TsuyoshiIto: No, I didn't expect that from readers. I just asked for some known results of some variants of a specific problem (Vertex-Cluster-Deletion) which was studied in the referenced paper. The case for two cliques is a particular case from the problem I described, because a cluster graph can have more or less than two cliques. I would try to edit question to let things more clear. Anyway, this discussion is pointless, if you think my question didn't follow the rules just report it to right people.  
> **username_1**: @user2582: I just wanted to decide whether I should think further about your question or not.  Now I decided not to bother.  
> **username_0**: @TsuyoshiIto: Sorry for making you lose time.  

---

