# Max weight k-clique

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?

• Clique problem is not approximable. Nov 22, 2016 at 4:11
• Is an approximation algorithm known to decide whether an $n$-vertex graph without edge weights is triangle free in $o(n^3)$ time? Nov 23, 2016 at 9:13
• @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. Nov 24, 2016 at 13:53

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

• dante is interested in "fixed size $k$ ($k$ is constant)", which that paper does not seem to address. ​ ​
– user6973
Nov 22, 2016 at 13:29
• @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). Nov 24, 2016 at 10:03
• @Saeed : ​ How are you defining $c$-approximation so that "if the answer is yes, then there is a $k$-clique, otherwise there isn't"? ​ ​ ​ ​
– user6973
Nov 25, 2016 at 4:58
• @RickyDemer, In the case that you don't know what is constant factor approximation please read the basic definition of constant factor approximation. 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. Nov 25, 2016 at 9:27
• @Saeed : ​ ​ ​ That page's definitions are the usual ones, which are for approximation problems, rather than ones with yes/no answers. ​ Furthermore, for all integers k that are greater than 2, for all graphs whose max-clique-size is in {k-1,k+1}, the graph has at least one (ceil(k/2))-clique and all such cliques are valid 3-approximations in the usual sense. ​ Thus, my previous comment's question stands. ​ ​ ​ ​
– user6973
Nov 25, 2016 at 15:48