Hello Does someone have an idea for heuristics for the problem:

Given undirected weighted(weights on edges) complete graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of nodes) having the minimum weight.

I have searched for minclique problem but it doesn't really answer my question. Thank you in advance.

  • $\begingroup$ Is k part of the input or a fixed constant? $\endgroup$ Oct 15, 2010 at 16:47
  • $\begingroup$ its part of the input $\endgroup$
    – YAKOVM
    Oct 15, 2010 at 16:48
  • 1
    $\begingroup$ weights on edges or vertices ? $\endgroup$ Oct 15, 2010 at 16:50
  • $\begingroup$ @Suresh: wieghts on edges $\endgroup$
    – YAKOVM
    Oct 15, 2010 at 16:55
  • $\begingroup$ please edit the problem defn to incorporate this. $\endgroup$ Oct 15, 2010 at 16:59

1 Answer 1


Your problem appears to be the minimization variant (flip the edge weight signs?) of the edge-weighted maximal clique problem. Check out this reference:

title={{An extended formulation approach to the edge-weighted maximal clique problem}},
author={Park, K. and Lee, K. and Park, S.},
journal={European Journal of Operational Research},
volume={95}, number={3},
publisher={Elsevier} }

where they discuss various LP-based heuristics.

  • $\begingroup$ The lp-heuristics is too slow but i will look for other algorithms $\endgroup$
    – YAKOVM
    Oct 15, 2010 at 20:30

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.