Optimization Online


Worst-case analysis of clique MIPs

Mohammad Javad Naderi(mnaderi***at***okstate.edu)
Austin Buchanan(buchanan***at***okstate.edu)
Jose L. Walteros(josewalt***at***buffalo.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/2021
Entry Accepted: 01/08/2021
Entry Last Modified: 01/07/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society