Parallel Bounded Search for the Maximum Clique Problem

Given an undirected graph, the Maximum Clique Problem (MCP) is to find a largest complete subgraph of the graph. MCP is NP-hard and has found many practical applications. In this paper, we propose a parallel Branch-and- Bound (BnB) algorithm to tackle this NP-hard problem, which carries out multiple...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer science and technology 2023-09, Vol.38 (5), p.1187-1202
Main Authors: Jiang, Hua, Bai, Ke, Liu, Hai-Jiao, Li, Chu-Min, Manyà, Felip, Fu, Zhang-Hua
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Artificial Intelligence
Computer Science
Data Structures and Information Theory
Graph theory
Information Systems Applications (incl.Internet)
Lower bounds
Optimization
Regular Paper
Searching
Software Engineering
Theory of Computation
Upper bounds
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given an undirected graph, the Maximum Clique Problem (MCP) is to find a largest complete subgraph of the graph. MCP is NP-hard and has found many practical applications. In this paper, we propose a parallel Branch-and- Bound (BnB) algorithm to tackle this NP-hard problem, which carries out multiple bounded searches in parallel. Each search has its upper bound and shares a lower bound with the rest of the searches. The potential benefit of the proposed approach is that an active search terminates as soon as the best lower bound found so far reaches or exceeds its upper bound. We describe the implementation of our highly scalable and efficient parallel MCP algorithm, called PBS, which is based on a state-of-the-art sequential MCP algorithm. The proposed algorithm PBS is evaluated on hard DIMACS and BHOSLIB instances. The results show that PBS achieves a near-linear speedup on most DIMACS instances and a super-linear speedup on most BHOSLIB instances. Finally, we give a detailed analysis that explains the good speedups achieved for the tested instances.
ISSN:1000-9000
1860-4749
DOI:10.1007/s11390-022-1803-8