Regularized standard polynomial programming formulations for the maximum clique problem

Recently, a novel hierarchy of standard polynomial programming formulations for the maximum clique problem has been proposed, inspired by the classical Motzkin–Straus formulation. The k-th formulation ( $${{\textbf {P}}}^k$$ P k ) in this hierarchy expresses the problem of finding a maximum clique in a given graph G as maximization of degree-k multi-linear polynomial over the standard simplex, and every local maximizer of ( $${{\textbf {P}}}^{k+1}$$ P k + 1 ) is also a local maximizer of ( $${{\textbf {P}}}^k$$ P k ) for $$k\in \{2,\ldots , \omega -1\}$$ k ∈ { 2 , … , ω - 1 } , where $$\omega $$ ω is the clique number of G. In particular, every local maximizer of ( $${{\textbf {P}}}^\omega $$ P ω ) is global. Similarly to Motzkin–Straus formulation, ( $${{\textbf {P}}}^k$$ P k ) allows “spurious” local maxima, whose support does not correspond to a clique and needs to be further processed to obtain a clique. This drawback motivated several regularizations of Motzkin–Straus formulation proposed in the literature. This paper generalizes one such regularization to ( $${{\textbf {P}}}^k$$ P k ), to ensure that each local maximizer of the regularized formulation corresponds to a maximal clique with at least $$k-1$$ k - 1 vertices in G, and vice versa. The performance of a local optimization solver on the original and proposed regularized formulations for $$k\in \{2, 3, 4, 5\}$$ k ∈ { 2 , 3 , 4 , 5 } is compared through extensive numerical experiments. The results indicate that both approaches are competitive and that the multi-linear structure of ( $${{\textbf {P}}}^k$$ P k ) can be advantageous to the correspondence between local maxima and maximal cliques ensured by regularized formulations.