Constant factor approximation of MAX CLIQUE

Abstract

MAX CLIQUE problem (MCP) is an NPO problem, which asks to find the largest complete sub-graph in a graph $G,G=(V,E)$ (directed or undirected). MCP is well known to be $NP-Hard$ to approximate in polynomial time with an approximation ratio of $1+\epsilon$, for every $\epsilon >0$ [9] (and even a polynomial time approximation algorithm with a ratio $n^{1-\epsilon }$ has been conjectured to be non-existent [2] for MCP). Up to this date, the best known approximation ratio for MCP of a polynomial time algorithm is $O(n(lo{g}_2(lo{g}_2(n)){)}^2/(lo{g}_2(n){)}^3)$ given by Feige [1]. In this paper, we show that MCP can be approximated with a constant factor in polynomial time through approximation ratio preserving reductions from MCP to MAX DNF and from MAX DNF to MIN SAT. A 2-approximation algorithm for MIN SAT was presented in [6]. An approximation ratio preserving reduction from MIN SAT to min vertex cover improves the approximation ratio to $2-\Theta (1/\sqrt{n})$ [10]. Hence we prove false the infamous conjecture, which argues that there cannot be a polynomial time algorithm for MCP with an approximation ratio of any constant factor.

the reduction does not preserve the approximation ratio