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

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

| cite | improve this answer | |
  • $\begingroup$ I like this formulation. This is possibly a proper formulation of the problem that I am trying to solve. $\endgroup$ – Hasan May 10 '16 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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