A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem
该论文为最大团问题建立了一个多项式规划公式的层次结构，将图的团数与一个多线性多项式函数在标准单纯形上的全局最大值联系起来，并证明高阶公式的局部最大值集合是低阶公式的子集。
The maximum clique problem is a classical optimization problem which finds many important applications. Some of the most theoretically interesting and computationally successful approaches to this problem are based on the Motzkin--Straus formulation, expressing the clique number in terms of the maximal value of a standard quadratic program. This intriguing relationship has also motivated significant developments in quadratic optimization, copositive programming, and complexity in nonlinear optimization. Inspired by such developments, this paper establishes a hierarchy of polynomial programming formulations (\textbfP$^k$), $k\in\{2,\ldots, \omega\}$ for the maximum clique problem, relating the clique number $\omega$ of a given graph to the global maximal value of a multilinear polynomial function $f_k(x)$ of degree $k$ over the standard simplex in $\mathbb{R}^{|V|}$. The case of $k=2$ corresponds to the Motzkin--Straus formulation, and the hierarchical feature is in the fact that the set of local maxima of (\textbfP$^{k+1}$) is a subset of the set of local maxima of (\textbfP$^{k}$), $k\in\{2,\ldots, \omega-1\}$. In particular, every local maximum of (\textbfP$^{\omega}$) is global.