The clique problem for graphs with a few eigenvalues of the same sign

The quadratic programming problem is known to be NP‐hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin‐Strauss quadratic formulation with a fixed number of negative eigenvalues (with multiplicities).