Maximal Clique partition of vertices with smallest number of cut edges
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 &gt; 0$ such that it is NP-hard to approximate Cluster Deletion to within a factor of $1 + \epsilon$.