2
$\begingroup$

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?

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

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

$\endgroup$
5
  • 1
    $\begingroup$ dante is interested in "fixed size $k$ ($k$ is constant)", which that paper does not seem to address. ​ ​ $\endgroup$
    – user6973
    Nov 22 '16 at 13:29
  • $\begingroup$ @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). $\endgroup$
    – Saeed
    Nov 24 '16 at 10:03
  • $\begingroup$ @Saeed : ​ How are you defining $c$-approximation so that "if the answer is yes, then there is a $k$-clique, otherwise there isn't"? ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 25 '16 at 4:58
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Nov 25 '16 at 9:27
  • $\begingroup$ @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. ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 25 '16 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.