Parallel Algorithms for Maximal-Clique Problems on Multi-Core Shared Memory Systems

Abstract

Maximal clique enumeration is combinatorial graph problem, which identifies the largest fully connected subgroups within a graph, uncovering tightly-knit communities and critical relationships essential for analyzing complex networks in social science, biology, and computer science. However, due to its exponen tial complexity, this combinatorial problem is computationally intensive. The Bron–Kerbosch algorithm is a popular method for finding maximal cliques, but its sequential execution limits performance on large-scale graphs. Previous methods mostly focused on GPU-based parallelization (using SIMD and data parallelism) and distributed memory systems. With the advent of multi-core processors in mainstream devices such as laptops, tablets, and mobiles, these machines now have the capability to leverage shared-memory par allelization. Utilizing the parallelism of multi-core hardware offers a promising way to improve execution efficiency on common platforms. However, prior shared-memory parallelization approaches often involving SIMD instruction sets and cloud resources, have not sufficiently simplified the parallelization process for mainstream machines. This study presents parallel implementations of the Bron–Kerbosch algorithm and its pivot variant using OpenMP, optimized for multi-core shared-memory systems. The parallel algorithms employ recursive decomposition and load balancing techniques while avoiding race conditions and duplicate results. Performance was evaluated by varying thread counts and input graph sizes, spanning sparse to dense graphs. Comparisons between parallel and serial versions on identical hardware demonstrate signifi cant speedups, with the pivot-based parallel variant showing superior load balancing and reduced redundant computations. These results confirm that shared-memory parallelism substantially improves scalability and execution time for maximal clique enumeration, making it a practical approach for large-scale combinatorial graph problems in mainstream machines.