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!
Maximal Clique partition of vertices with smallest number of cut edges
clique;partition problem
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):173182, 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$.