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

<blockquote>
  <p>@article{park1996extended,<br>
  title={{An extended formulation
  approach to the edge-weighted maximal
  clique problem}},<br>
  author={Park, K.
  and Lee, K. and Park, S.},<br>
  journal={European Journal of
  Operational Research},<br>
  volume={95}, 
  number={3},<br>
  pages={671--682},<br>
  year={1996},<br>
  publisher={Elsevier} }</p>
</blockquote>

<p>where they discuss various LP-based heuristics. </p>

CC BY-SA 2.5
2010-10-15T20:30:04.833Z
The lp-heuristics is too slow but i will look for other algorithms
YAKOVM
CC BY-SA 2.5
2010-10-15T17:03:40.900Z
2010-10-15T17:03:40.900Z
Suresh Venkat
<p>Hello
Does someone have an idea for heuristics for the problem:</p>

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

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

CC BY-SA 2.5
2010-10-15T16:47:11.143Z
Is k part of the input or a fixed constant?
Robin Kothari
CC BY-SA 2.5
2010-10-15T16:48:59.643Z
its part of the input
YAKOVM
CC BY-SA 2.5
2010-10-15T16:50:08.413Z
weights on edges or vertices ?
Suresh Venkat
CC BY-SA 2.5
2010-10-15T16:55:45.117Z
@Suresh: wieghts on edges
YAKOVM
CC BY-SA 2.5
2010-10-15T16:59:14.680Z
please edit the problem defn to incorporate this.
Suresh Venkat
CC BY-SA 2.5
2010-10-15T16:59:55.253Z
How big are the $k$, $m$ and $n$ you have in mind? Do your weights satisfy any nice properties such as density (i.e. max weight = O(sum of weights / $n^2$))? Your problem sounds like it's a weighted version of the densest subgraph problem, so you may wish to search for algorithms for that problem for ideas.
Warren Schudy
CC BY-SA 2.5
2010-10-15T17:06:32.257Z
@Warren Schudy Maybe I have not searched right but what I have found talks about maximum and not minimum. Please correct me if I wrong.
YAKOVM
CC BY-SA 2.5
2010-10-15T17:18:13.993Z
@Yakov, for the algorithms that I know of, all you have to do is flip the signs of all weights to find the minimum weight clique. For example, all the papers I'm on that say anything about "maximum weight triangle" are equally valid when maximum is replaced with minimum. (The algorithms have to change only mildly.)
Ryan Williams
CC BY-SA 2.5
2010-10-15T18:38:32.143Z
@Yakov: as Ryan said it's easy to convert between minimization and maximization by just flipping the signs of the weights.
Warren Schudy
<ds.algorithms><graph-theory><graph-algorithms><clique><heuristics>
Heuristics for the minimum-weight $k$-clique problem
YAKOVM
# Heuristics for the minimum-weight $k$-clique problem

(Asked by: username_0 on 2010-10-15)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, clique, heuristics

> **Comments:**
> **username_1**: Is k part of the input or a fixed constant?  
> **username_0**: its part of the input  
> **username_2**: weights on edges or vertices ?  
> **username_0**: @Suresh: wieghts on edges  
> **username_2**: please edit the problem defn to incorporate this.  
> **username_3**: How big are the $k$, $m$ and $n$ you have in mind? Do your weights satisfy any nice properties such as density (i.e. max weight = O(sum of weights / $n^2$))? Your problem sounds like it's a weighted version of the densest subgraph problem, so you may wish to search for algorithms for that problem for ideas.  
> **username_0**: @username_3 Maybe I have not searched right but what I have found talks about maximum and not minimum. Please correct me if I wrong.  
> **username_4**: @Yakov, for the algorithms that I know of, all you have to do is flip the signs of all weights to find the minimum weight clique. For example, all the papers I'm on that say anything about "maximum weight triangle" are equally valid when maximum is replaced with minimum. (The algorithms have to change only mildly.)  
> **username_3**: @Yakov: as Ryan said it's easy to convert between minimization and maximization by just flipping the signs of the weights.  

---

## 1 answers

### Answer by username_2 on 2010-10-15. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: The lp-heuristics is too slow but i will look for other algorithms  

---

