Distributed maximum clique computation via clique-preserving partitioning and vertex replication
Future Generation Computer Systems, cilt.187, 2027 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 187
- Basım Tarihi: 2027
- Doi Numarası: 10.1016/j.future.2026.108791
- Dergi Adı: Future Generation Computer Systems
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Compendex, INSPEC, zbMATH, Business Source Ultimate (EBSCO), Engineering Source (EBSCO)
- Anahtar Kelimeler: Distributed computing, Graph partitioning, Maximum clique, Parallel programming, Point cloud registration
- Ankara Yıldırım Beyazıt Üniversitesi Adresli: Evet
Özet
The maximum clique problem is a fundamental NP-hard problem in graph theory. Despite advances in exact and heuristic solvers, their performance on large graphs is limited by irregular search spaces, strong sequential dependencies in pruning, and pronounced load imbalance. Parallel execution is therefore necessary to address these challenges, but achieving high performance without degrading solution quality is nontrivial. In this work, we propose a distributed-memory framework for the maximum clique problem based on structure-aware graph decomposition that preserves clique structure. The framework integrates controlled boundary vertex replication to maintain global clique integrity while enabling efficient parallel execution. Experimental results on large real-world and benchmark graphs demonstrate that the proposed framework achieves substantial parallel speedups on an HPC cluster while maintaining high solution quality. With 16 processors and a replication ratio of 1%, the framework preserves the maximum clique on the majority of real-world graph instances, achieving an average speedup of approximately (Formula presented) and peak speedups of up to (Formula presented). Additional experiments with a fundamentally different maximum clique solver indicate that the framework is largely independent of the underlying clique-search strategy. We further provide theoretical guarantees that characterize when graph partitioning preserves the maximum clique and quantify the replication required to recover cliques fragmented by partitioning.