Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs

Hua Jiang (1) , Chu-Min Li (2, 3) , Felip Manya (4)

1 University of Colorado [Colorado Springs]
2 COALA - COntraintes, ALgorithmes et Applications
3 MIS - Modélisation, Information et Systèmes - UR UPJV 4290
4 IIIA / CSIC - Artificial Intelligence Research Institute / Spanish Scientific Research Council

We describe a new exact algorithm for MaxClique, called LMC (short for Large MaxClique), that is especially suited for large sparse graphs. LMC is competitive because it combines an efficient preprocessing procedure and incremental MaxSAT reasoning in a branch-and-bound scheme. The empirical results show that LMC outperforms existing exact MaxClique algorithms on large sparse graphs from real-world applications.

Domaines: Informatique [cs]

Hua Jiang, Chu-Min Li, Felip Manya. Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs. ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, Aug 2016, The Hague, Netherlands. pp.939-947, ⟨10.3233/978-1-61499-672-9-939⟩. ⟨hal-03636430⟩