The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound
Preprint
Abstract
Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core 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.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Initial Sorting of Vertices in the Maximum Clique Problem Reviewed2014
- Self-splitting of Workload in Parallel Computation2014
- Parallel Combinatorial Optimization with Decision Diagrams2014
- Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other EnhancementsSpringer Proceedings in Mathematics & Statistics, 2013
- Experiments in Parallel Constraint-Based Local Search2011
- Algorithmic Skeletons for Branch and BoundCommunications in Computer and Information Science, 2008
- Parallel Algorithm Design for Branch and Bound2006
- Parallel Branch‐and‐Bound Algorithms2006
- Using Constraint Programming to Solve the Maximum Clique ProblemLecture Notes in Computer Science, 2003
- Asynchronous parallel branch and bound and anomaliesLecture Notes in Computer Science, 1995