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!

  • $\begingroup$ What is the parameter that you are optimizing? Is it the total number of edges outside the cliques? $\endgroup$ Commented Apr 29, 2016 at 13:02
  • $\begingroup$ Also, is it mandatory that the cliques are maximal? (i.e, are not contained in larger cliques) $\endgroup$ Commented Apr 29, 2016 at 13:02
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Clique_cover_problem is already NP-complete. $\endgroup$ Commented Apr 29, 2016 at 13:05
  • $\begingroup$ 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. $\endgroup$
    – tarulen
    Commented Apr 29, 2016 at 14:35
  • 1
    $\begingroup$ That is false. The single vertex is not a maximal clique. $\endgroup$ Commented May 8, 2016 at 18:32

1 Answer 1


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

  • $\begingroup$ I like this formulation. This is possibly a proper formulation of the problem that I am trying to solve. $\endgroup$
    – Hasan
    Commented May 10, 2016 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.