# Heuristics for the minimum-weight $k$-clique problem

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.

• Is k part of the input or a fixed constant? Oct 15 '10 at 16:47
• its part of the input Oct 15 '10 at 16:48
• weights on edges or vertices ? Oct 15 '10 at 16:50
• @Suresh: wieghts on edges Oct 15 '10 at 16:55
• please edit the problem defn to incorporate this. Oct 15 '10 at 16:59

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

@article{park1996extended,
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},
pages={671--682},
year={1996},
publisher={Elsevier} }

where they discuss various LP-based heuristics.

• The lp-heuristics is too slow but i will look for other algorithms Oct 15 '10 at 20:30