Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation (Q2401518)

A continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix is presented. A one-to-one correspondence between stationary points of the authors' formulation and cliques of a given graph is built. It is shown that the local (resp. global) minima of the continuous problem correspond to the maximal (resp. maximum) cliques of the given graph. A new clique finding algorithm based on the continuous formulation is presented. The efficiency of the new algorithm is tested on the DIMACS data sets to show that it outperforms other existing algorithms based on the Motzkin-Straus formulation and that it can compete with a sophisticated combinatorial heuristic.