# Maximal Clique partition of vertices with smallest number of cut edges

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?

• What is the parameter that you are optimizing? Is it the total number of edges outside the cliques? – Igor Shinkar Apr 29 '16 at 13:02
• Also, is it mandatory that the cliques are maximal? (i.e, are not contained in larger cliques) – Igor Shinkar Apr 29 '16 at 13:02
• en.wikipedia.org/wiki/Clique_cover_problem is already NP-complete. – András Salamon Apr 29 '16 at 13:05
• 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 Apr 29 '16 at 14:35
• That is false. The single vertex is not a maximal clique. – David Eppstein May 8 '16 at 18:32

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