Combining Graph Structure Exploitation and Propositional Reasoning for the Maximum Clique Problem
Chu-Min Li, Zhe Quan · 2010
State-of-the-art branch-and-bound algorithms for the maximum clique problem (Maxclique) generally exploit the structural information of a graph G to partition G into independent sets, in order to derive an upper bound for the cardinality of a maximum clique of G, which cannot be very tight for imperfect graphs. On the other hand, while Maxclique can be easily encoded into MaxSAT to be solved using a MaxSAT solver, general-purpose MaxSAT solvers are not competitive for solving Maxclique, because they do not exploit the structural information of the graph. Recently, we have shown that propositional reasoning developed for the MaxSAT solvers can be used to improve the upper bound based on the partition. In this paper, we propose and study several improvements to this approach by better combining graph structure exploitation and propositional reasoning to solve Maxclique. Experimental results show that the improvements are very effective on hard random graphs and on DIMACS Maxclique benchmarks which are widely used to evaluate branch-and-bound algorithms for Maxclique.