Copositivity cuts for improving SDP bounds on the clique number
Adding cuts based on copositive matrices, we propose to improve Lovasz' bound theta on the clique number and its tightening theta' introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies starting with theta' rapidly increases with the order (and quality requirements). By contrast, the bounds proposed here are relatively cheap in the sense that computational effort is comparable to that required for theta'.
lovasz' bound semidefinite programming maximum clique problem