A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs

摘要

Given an undirected graph with positive weights on the vertices, the Maximum Weight Clique Problem (MWCP) consists in finding a clique with maximum total weight. In this paper, we present a CPU-GPU local search heuristic for solving the MWCP on massive graphs. The heuristic is based on two new neighborhood structures for the problem. These neighborhoods are explored using an efficient procedure that is suitable to be mapped onto a GPU-based massively parallel architecture. We test the proposed heuristic on real-world massive graphs with millions of edges and vertices. The results indicate that, even when the heuristic is executed on a CPU-only architecture, it is able to outperform the best-known heuristics for the MWCP. Moreover, the hybrid CPU-GPU implementation obtained an average speedup of up to 12 times over the CPU-only implementation. (C) 2017 Elsevier Ltd. All rights reserved.