A parallel optimization algorithm for the maximum clique problem. (c2008)

Abstract

Recent advances in exact algorithm design and multi-processor industry have led to an increasing interest in exact (or optimal) solutions for hard problems. This interest was also motivated by the emergence of parameterized complexity theory as well as the recent discouraging hardness of approximation results for most intractable problems. Coupling the best exact algorithms with scalable parallel implementations is a promising approach for dealing with computationally demanding problems. In this work, we introduce a parallel technique for solving the Maximum Clique problem using clusters of multi-core machines. Our algorithm employs a scalable load balancing strategy that is based on dynamic search-tree decomposition. We present experimental results that verify the scalability of our technique and its utility as a better alternative to approximation algorithms in many practical applications.