<p>Your problem is very hard to approximate, even in the case where all weights are just $0$ or $1$:</p>

<blockquote>
  <p>Pasin Manurangsi:<br>
  Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph<br>
  <a href="https://arxiv.org/abs/1611.05991" rel="nofollow noreferrer">https://arxiv.org/abs/1611.05991</a></p>
</blockquote>

CC BY-SA 3.0
2016-11-24T10:03:21.197Z
@RickyDemer, If there was a $c$-approximation for a fixed $k$ in time $n^{c_1}$, then one can find $k$ clique in time $n^{c_1}$: Use the approximation algorithm for $c\cdot k$ clique, if the answer is yes, then there is a $k$-clique, otherwise there isn't. But $k$-clique is not $n^{o(k)}$ solvable (assuming ETH).
Saeed
CC BY-SA 3.0
2016-11-25T09:27:35.137Z
@RickyDemer, In the case that you don't know what is constant factor approximation please read the basic definition of constant factor approximation. https://en.wikipedia.org/wiki/APX. Anyway here we can replace c with some function of k. If you don't know what is constant factor approximation of k-clique, then in simple words: Like many other maximization approximation, it means if there is a k-clique, then finds k/c clique in polynomial time.
Saeed
CC BY-SA 3.0
2016-11-22T11:05:05.450Z
2016-11-22T11:05:05.450Z
Gamow
<p>Given an edge-weighted directed complete graph $G = (V,A)$, the maximum weight clique of fixed size $k$ ($k$ is a constant) can be identified in polynomial time with a brute-force algorithm, however the running time is impractical if $k$ is reasonably large.</p>

<p>Is there a heuristic with provable approximation guarantees? Or any conditions on the weights that makes this problem easier?</p>

CC BY-SA 3.0
2016-11-22T04:11:28.537Z
Clique problem is not approximable.
Saeed
CC BY-SA 3.0
2016-11-23T09:13:13.850Z
Is an approximation algorithm known to decide whether an $n$-vertex graph without edge weights is triangle free in $o(n^3)$ time?
András Salamon
CC BY-SA 3.0
2016-11-24T13:53:17.787Z
@András Salamon: Deciding the existence of a triangle in an $n$-vertex graph can be done in $O(n^{2.38})$ time by matrix multiplication.
Gamow
<graph-theory><graph-algorithms><clique>
Max weight k-clique
dante
# Max weight k-clique

(Asked by: username_0 on 2016-11-21)

Given an edge-weighted directed complete graph $G = (V,A)$, the maximum weight clique of fixed size $k$ ($k$ is a constant) can be identified in polynomial time with a brute-force algorithm, however the running time is impractical if $k$ is reasonably large.

Is there a heuristic with provable approximation guarantees? Or any conditions on the weights that makes this problem easier?

**Tags:** graph-theory, graph-algorithms, clique
> **Comments:**
> **username_1**: Clique problem is not approximable.  
> **username_2**: Is an approximation algorithm known to decide whether an $n$-vertex graph without edge weights is triangle free in $o(n^3)$ time?  
> **username_3**: @András Salamon: Deciding the existence of a triangle in an $n$-vertex graph can be done in $O(n^{2.38})$ time by matrix multiplication.  

---

## 1 answers

### Answer by username_3 on 2016-11-22. Score: 2

Your problem is very hard to approximate, even in the case where all weights are just $0$ or $1$:

> Pasin Manurangsi:  
> Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph  
> <https://arxiv.org/abs/1611.05991>

> **Comments:**
> **username_1**: @RickyDemer, If there was a $c$-approximation for a fixed $k$ in time $n^{c_1}$, then one can find $k$ clique in time $n^{c_1}$: Use the approximation algorithm for $c\cdot k$ clique, if the answer is yes, then there is a $k$-clique, otherwise there isn't. But $k$-clique is not $n^{o(k)}$ solvable (assuming ETH).  
> **username_1**: @RickyDemer, In the case that you don't know what is constant factor approximation please read the basic definition of constant factor approximation. https://en.wikipedia.org/wiki/APX. Anyway here we can replace c with some function of k. If you don't know what is constant factor approximation of k-clique, then in simple words: Like many other maximization approximation, it means if there is a k-clique, then finds k/c clique in polynomial time.  

---

