  


Worstcase analysis of clique MIPs
Mohammad Javad Naderi(mnaderiokstate.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 branchandbound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worstcase 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)$ branchandbound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes, $O(1.62^d n)$. Further, when a bestbound node selection strategy is used, $O(2^g n)$ nodes are visited, where $g=(d+1)\omega$ is the cliquecore 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; branchandbound; fixedparameter tractability; clique; kcore; degeneracy; cliquecore gap; Category 1: Integer Programming (01 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 Modify/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  