A CLP approach for solving the maximum clique problem: Benefits and limits

Abstract

© 2017 IEEE. Maximal Clique and Maximum Clique are two related and famous computational problems known to be intractable in the most general case. We propose a formulation of the Maximal Clique problem as a Boolean Satisfaction problem. The constraints are then mapped to a Constraint Logic Programming representation. The resulting representation can be input to a Constraint Logic Programming system that can be used in combination with a suitable Branch-and-Bound search strategy to compute the Clique Number and the Maximum Clique of a given undirected graph. We present initial experimental results that we obtained with this approach by utilizing ECLiPSe-CLP as target implementation platform. We also discuss the potential benefits, as well as the limitations, of this approach.