<p>This problem is the Cluster Edge Deletion problem.</p>

<blockquote>
  <p>Given a graph $G = (V,E)$ and an integer, can we delete at most $k$ edges $F \subseteq E$ such that $G-F$ is a <em>cluster graph</em>?</p>
</blockquote>

<p>A cluster graph here is a graph whose connected components are cliques.</p>

<p>The approximability of Cluster (Edge) Deletion, was studied by Shamir, Sharan, and Tsur (<em>Cluster graph modification problems.</em> Discrete Applied Mathematics, 144(1):173–182, 2004).  They show that the problem is <strong>NP-hard to approximate within a constant factor</strong>:</p>

<blockquote>
  <p><strong>Theorem 12.</strong> There is some constant $\epsilon &gt; 0$ such that it is NP-hard to approximate Cluster Deletion to within a factor of $1 + \epsilon$.</p>
</blockquote>

CC BY-SA 3.0
2016-05-10T16:07:49.473Z
I like this formulation. This is possibly a proper formulation of the problem that I am trying to solve.
Hasan
CC BY-SA 3.0
2016-05-08T09:27:39.557Z
2016-05-08T09:27:39.557Z
John K.
<p>I am given a simple undirected graph $G(V, E)$. I want to partition $V$ into $b$ Maximal cliques: $\{C_1, C_2, ..., C_b\}$ such that the number of edges that cut across two cliques is the minimum. $b$ is arbitrary i.e. there is no restriction on $b$.</p>

<p>I think the decision version of this problem is NP-Complete. It may be reduced to a weighted independent set problem. My question is:</p>

<p>Is there any known approximate algorithm for this problem?</p>

<p>Thank you for your answers!</p>

CC BY-SA 3.0
2016-04-29T13:02:15.667Z
What is the parameter that you are optimizing? Is it the total number of edges outside the cliques?
Igor Shinkar
CC BY-SA 3.0
2016-04-29T13:02:57.137Z
Also, is it mandatory that the cliques are maximal? (i.e, are not contained in larger cliques)
Igor Shinkar
CC BY-SA 3.0
2016-04-29T13:05:11.087Z
https://en.wikipedia.org/wiki/Clique_cover_problem is already NP-complete.
András Salamon
CC BY-SA 3.0
2016-04-29T14:35:27.427Z
It could fall into the big family of **clustering** problems (splitting a graph into dense subgraphs with few edges in between)... you can always try to look for papers with this keyword.
tarulen
CC BY-SA 3.0
2016-04-29T22:42:16.227Z
Hi Igor, Yes, I am optimizing the total number of edges that are outside the cliques. And, yes it is required that that the cliques are maximal, otherwise one can simply consider 2-sized cliques and find a maximum matching solution where the optimal solution is be number of unmatched edges.
Hasan
CC BY-SA 3.0
2016-04-29T23:05:05.670Z
Hi  András, Yes, it is has similarity to clique cover problem. But the objective is different. Here I want to minimize the number of edges that are outside the cliques, but traditional clique cover problem minimize the number of cliques.
Hasan
CC BY-SA 3.0
2016-04-29T23:12:49.910Z
Hi tarulen, Yes, it falls into some form of graph clustering where each partition is dense subgraph. However, I am explicitly looking for maximal clique as each partition, and want to optimize the number of cut edges. I am almost certain that it is NP-complete, so I am looking for a solution that can give some approximation guarantee. Thanks
Hasan
CC BY-SA 3.0
2016-04-30T21:09:04.320Z
What do you want to have happen when the graph has no such partition (as, for instance, the diamond graph formed by removing an edge from $K_4$ doesn't)?
David Eppstein
CC BY-SA 3.0
2016-05-01T02:59:10.693Z
Following up on David Eppstein's question, is it clear that the decision version of the problem is poly-time solvable? That is, can we decide whether G can be partitioned into p maximal cliques? It is probably hard by appropriate modification from the standard clique cover/coloring hardness reduction.
Chandra Chekuri
CC BY-SA 3.0
2016-05-02T22:47:46.587Z
David, for a diamond graph we have two maximal cliques: one is a triangle (3 vertices) and the other is a single vertex (no edge). The optimal solution is 2 as there are two edges crossing these two partitions.
Hasan
CC BY-SA 3.0
2016-05-08T18:32:07.610Z
That is false. The single vertex is not a maximal clique.
David Eppstein
CC BY-SA 3.0
2016-05-10T16:06:31.560Z
Agree, the problem is ill-defined. Thanks David and chandra
Hasan
<clique><partition-problem>
Maximal Clique partition of vertices with smallest number of cut edges
Hasan
# Maximal Clique partition of vertices with smallest number of cut edges

(Asked by: username_0 on 2016-04-29)

I am given a simple undirected graph $G(V, E)$. I want to partition $V$ into $b$ Maximal cliques: $\{C\_1, C\_2, ..., C\_b\}$ such that the number of edges that cut across two cliques is the minimum. $b$ is arbitrary i.e. there is no restriction on $b$.

I think the decision version of this problem is NP-Complete. It may be reduced to a weighted independent set problem. My question is:

Is there any known approximate algorithm for this problem?

Thank you for your answers!

**Tags:** clique, partition-problem
> **Comments:**
> **username_1**: What is the parameter that you are optimizing? Is it the total number of edges outside the cliques?  
> **username_1**: Also, is it mandatory that the cliques are maximal? (i.e, are not contained in larger cliques)  
> **username_2**: https://en.wikipedia.org/wiki/Clique_cover_problem is already NP-complete.  
> **username_3**: It could fall into the big family of **clustering** problems (splitting a graph into dense subgraphs with few edges in between)... you can always try to look for papers with this keyword.  
> **username_0**: Hi Igor, Yes, I am optimizing the total number of edges that are outside the cliques. And, yes it is required that that the cliques are maximal, otherwise one can simply consider 2-sized cliques and find a maximum matching solution where the optimal solution is be number of unmatched edges.  
> **username_0**: Hi  András, Yes, it is has similarity to clique cover problem. But the objective is different. Here I want to minimize the number of edges that are outside the cliques, but traditional clique cover problem minimize the number of cliques.  
> **username_0**: Hi tarulen, Yes, it falls into some form of graph clustering where each partition is dense subgraph. However, I am explicitly looking for maximal clique as each partition, and want to optimize the number of cut edges. I am almost certain that it is NP-complete, so I am looking for a solution that can give some approximation guarantee. Thanks  
> **username_4**: What do you want to have happen when the graph has no such partition (as, for instance, the diamond graph formed by removing an edge from $K_4$ doesn't)?  
> **username_5**: Following up on David Eppstein's question, is it clear that the decision version of the problem is poly-time solvable? That is, can we decide whether G can be partitioned into p maximal cliques? It is probably hard by appropriate modification from the standard clique cover/coloring hardness reduction.  
> **username_0**: David, for a diamond graph we have two maximal cliques: one is a triangle (3 vertices) and the other is a single vertex (no edge). The optimal solution is 2 as there are two edges crossing these two partitions.  
> **username_4**: That is false. The single vertex is not a maximal clique.  
> **username_0**: Agree, the problem is ill-defined. Thanks David and chandra  

---

## 1 answers

### Answer by username_6 on 2016-05-08. Score: 1 | Accepted answer

This problem is the Cluster Edge Deletion problem.

> Given a graph $G = (V,E)$ and an integer, can we delete at most $k$ edges $F \subseteq E$ such that $G-F$ is a *cluster graph*?

A cluster graph here is a graph whose connected components are cliques.

The approximability of Cluster (Edge) Deletion, was studied by Shamir, Sharan, and Tsur (*Cluster graph modification problems.* Discrete Applied Mathematics, 144(1):173–182, 2004). They show that the problem is **NP-hard to approximate within a constant factor**:

> **Theorem 12.** There is some constant $\epsilon > 0$ such that it is NP-hard to approximate Cluster Deletion to within a factor of $1 + \epsilon$.

> **Comments:**
> **username_0**: I like this formulation. This is possibly a proper formulation of the problem that I am trying to solve.  

---

