- Worst-case analysis of clique MIPs Mohammad Javad Naderi(mnaderiokstate.edu) Austin Buchanan(buchananokstate.edu) Jose L. Walteros(josewaltbuffalo.edu) Abstract: 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. Keywords: integer program; branch-and-bound; fixed-parameter tractability; clique; k-core; degeneracy; clique-core gap; Category 1: Integer Programming (0-1 Programming ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Combinatorial Optimization Citation: Submitted to a journal Download: [PDF]Entry Submitted: 01/07/2021Entry Accepted: 01/08/2021Entry Last Modified: 01/07/2021Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.