NK-PMC: A new exact branch and bound parallel algorithm for the maximum clique problem

Abstract For a given graph, finding a clique of maximum size is a well-known NP-hard problem that is a fundamental problem in combinatorial optimization and real-world applications. This paper reduces the problem into some smaller independent sub-problems and presents an efficient parallel algorithm. For each vertex, a core number-based sub-set of its neighbors is defined and shown that the maximum clique, including the vertex, is a subset of one of these neighbor sub-sets. Accordingly, we can define sub-problems to find the maximum clique by searching on the neighbor sub-sets separately, and create the independent sub-problems that can be solved in parallel. An other advantage is that our search areas are the neighbor sub-sets that, relative to the neighbor sets, have smaller sizes. Computational experiments demonstrate that the proposed algorithm outperforms the previous well-known algorithm for many instances when applied to DIMACSbenchmark graphs and a number of real-world networks.