The Shape of the Search Tree for the Maximum Clique Problem and the Implications for Parallel Branch and Bound
Ciaran McCreesh, Patrick Prosser · ACM Transactions on Parallel Computing · 2015
Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multicore thread-parallel adaptations of a state-of-the-art branch-and-bound algorithm for the maximum clique problem and provide a novel explanation as to why they are successful. We show that load balance is sometimes a problem but that the interaction of parallel search order and the most likely location of solutions within the search space is often the dominating consideration. We use this explanation to propose a new low-overhead, scalable work-splitting mechanism. Our approach uses explicit early diversity to avoid strong commitment to the weakest heuristic advice and late resplitting for balance. More generally, we argue that, for branch-and-bound, parallel algorithm design should not be performed independently of the underlying sequential algorithm.