1
$\begingroup$

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!

Improve this question
$\endgroup$
12
  • $\begingroup$ What is the parameter that you are optimizing? Is it the total number of edges outside the cliques? $\endgroup$
    – Igor Shinkar
    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$
    – Igor Shinkar
    Apr 29, 2016 at 13:02
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Clique_cover_problem is already NP-complete. $\endgroup$
    – András Salamon
    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
    Apr 29, 2016 at 14:35
  • 1
    $\begingroup$ That is false. The single vertex is not a maximal clique. $\endgroup$
    – David Eppstein
    May 8, 2016 at 18:32

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Your Answer

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

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