Worst-case analysis of clique MIPs

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 ^dn) branch-and-bound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes, O(1. 62 ^dn). Further, when a best-bound node selection strategy is used, O(2 ^gn) nodes are visited, where g= (d+ 1) - ω 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.