The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we propose has just $O(n+m)$ nonzeros for graphs with $n$ vertices and $m$ edges. Nevertheless, it ensures a root LP bound of at most $d+1$, where $d$ denotes the graph’s degeneracy (a measure of density), and is solved in $O(2^d n)$ branch-and-bound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes, $O(1.62^d n)$. Further, when a best-bound node selection strategy is used, $O(2^g n)$ nodes are visited, where $g=(d+1)-\omega$ is the clique-core gap. Often, $g$ is so small that it can be treated as a constant in which case $O(n)$ nodes are visited. Experiments are conducted to understand their performance in practice.
Citation
Submitted to a journal