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 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.

中文摘要：

研究背景：最大团问题是图论中经典的组合优化问题，除了自身的理论价值，在诸如故障诊断、生物信息学、编码理论、经济学、计算机视觉和社交网络分析中也存在广泛的应用。以分支限界的算法为代表的精确算法，在过去20年中取得了长足的进步。然而，由于最大团问题本身固有的NP难解特性，精确算法在有限时间内能够解决的问题规模仍然十分有限。常用的算法加速方法，不仅可以充分利用现代多核处理器的硬件优势实现加速，好的算法并行策略甚至能够实现超越硬件使用比例的超线性加速。因此算法并行化是提升问题求解时间效率重要途径。
目的：本文研究最大团问题分支限界算法的并行化方法。我们提出了一种简单高效且易于扩展的并行化策略。通过该并行策略提升现有最大团问题精确算法的时间效率、增强算法的现实可用性。
方法：本文提出称为并行限界搜索的并行搜索策略。该策略将整个图的最大团搜索任务，分解为多个子图上的搜索任务，同时为每个子搜索任务计算一个紧致的上界。被分解的子任务被并行地执行，并共享公共的最新最大团下界。一旦更优的下界被更新，正在执行的子任务，由于其上界不大于新下界可能被提前终止，从而达到搜索剪枝的目的。本文主要研究如何实现子任务分解和协作，以最大程度地实现搜索剪枝。
结果：我们从理论和实验两个方面对算法的实际加速效果进行了分析和评估。结果表明新的算法在大多数测试算例上均达到了线性加速效果，在部分算例上甚至到了明显的超线性加速效果。在BHOSLIB测试集上，我们首次报告了除最大图（frb100）以外的全部算例的求解结果。
结论：理论分析和实验结果证明本文提出的并行限界搜索策略在对最大团分支限界算法的并行化上非常有效。新的算法在多数BHOSLIB实例上都实现了超线性加速效果。此外，该并行限界搜索策略的实现简单、易于扩展，使得提高算法并行程度变得更加容易，可以进一步降低精确算法的实际执行时间，提高了精确算法的现实可用性。

Key words: branch-and-bound; maximum clique problem; parallel search;