A complementary pivoting approach to the maximum weight clique problem

Given an undirected graph with positive weights on the vertices, the maximum weight clique problem (MWCP) is to find a subset of mutually adjacent vertices (i.e., a clique) having largest total weight. The problem is known to be NP-hard, even to approximate. Motivated by a recent quadratic programming formulation, which generalizes an earlier remarkable result of Motzkin and Straus, in this paper we propose a new framework for the MWCP based on the corresponding linear complementarity problem (LCP). We show that, generically, all stationary points of the MWCP quadratic program exhibit strict complementarity. Despite this regularity result, however, the LCP turns out to be inherently degenerate, and we find that Lemke's well-known pivoting method, equipped with standard degeneracy resolution strategies, yields unsatisfactory experimental results. We exploit the degeneracy inherent in the problem to develop a variant of Lemke's algorithm which incorporates a new and effective look-ahead pivot rule. The resulting algorithm is tested extensively on various instances of random as well as DIMACS benchmark graphs, and the results obtained show the effectiveness of our method.