An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem

Chu Min Li, Zhe QuanAAAI 2010 · OpenReview

Abstract

State-of-the-art branch-and-bound algorithms for the maximum clique problem (Maxclique) frequently use an upper bound based on a partition $P$ of a graph into independent sets for a maximum clique of the graph, which cannot be very tight for imperfect graphs. In this paper we propose a new encoding from Maxclique into MaxSAT and use MaxSAT technology to improve the upper bound based on the partition $P$. In this way, the strength of specific algorithms for Maxclique in partitioning a graph and the strength of MaxSAT technology in propositional reasoning are naturally combined to solve Maxclique. Experimental results show that the approach is very effective on hard random graphs and on DIMACS Maxclique benchmarks, and allows to close an open DIMACS problem.

Introduction

The Maximum Clique problem (Maxclique)—finding the largest subset of vertices in a graph where every vertex is connected to every other—is a fundamental NP-hard problem with extensive applications in bioinformatics, social network analysis, and more. Most exact solvers employ a branch-and-bound strategy, which relies heavily on a "tight" upper bound to prune the search space effectively. Traditionally, these bounds are derived from graph coloring; since no two vertices of the same color can belong to the same clique, the number of colors provides a valid upper bound. However, for "imperfect" graphs, this bound is often loose, leading to inefficient search.

This paper introduces MaxCLQ, a high-performance solver that leverages advanced propositional reasoning from the MaxSAT (Maximum Satisfiability) domain to derive significantly tighter upper bounds.

Methodology

The core innovation of MaxCLQ lies in bridging graph theory and Boolean logic through a novel MaxSAT encoding.

Independent Set Encoding

Rather than using a standard MaxSAT encoding with one soft clause per vertex, the authors partition the graph into independent sets. They create one soft clause for each independent set. Since an independent set can contribute at most one vertex to any clique, this encoding is more compact and captures the graph's inherent structure more effectively.

MaxCLQ Algorithm and Pruning

MaxCLQ is a branch-and-bound solver that dynamically re-partitions subgraphs at every node of the search tree. At each step, it employs standard MaxSAT techniques such as Unit Propagation and Failed Literal Detection. By identifying "disjoint inconsistent subsets" of clauses—sets of independent sets that cannot simultaneously contribute to a clique—the algorithm can subtract them from the upper bound. This dynamic reasoning adapts to the local constraints of the subgraph, providing a much tighter constraint than simple coloring.

Experimental Evaluation

The algorithm was evaluated against random graphs and the standard DIMACS Maxclique benchmark suite.

Performance comparison of MaxCLQ against state-of-the-art solvers on random graphs.

Key Results

  • Superiority on Dense Graphs: On hard random graphs and dense DIMACS instances (e.g., the brock and san families), MaxCLQ outperformed state-of-the-art solvers like Cliquer, MCR, and MCQdyn, often by orders of magnitude.
  • Pruning Efficiency: As shown in the experimental data, the MaxSAT-based bound achieved a success rate (pruning rate) of up to 93% on dense graphs, demonstrating that the computational overhead of MaxSAT reasoning is well-justified by the reduction in search space.
  • Closing an Open Problem: Notably, MaxCLQ successfully solved the p_hat1000-3 DIMACS problem for the first time using an exact method.
Experimental results on DIMACS benchmarks, including the previously unsolved p_hat1000-3 instance.

Conclusion

MaxCLQ demonstrates that integrating structural graph information into a MaxSAT framework significantly enhances the performance of exact Maxclique solvers. While the complex reasoning introduces overhead on sparse graphs (density < 0.7) where simpler algorithms like MCR remain faster, it is highly effective for hard, dense instances. Future work includes integrating more sophisticated MaxSAT inference rules and testing on the BHOSLIB benchmark suite to further evaluate its robustness against "hidden" optimum instances.

Summary updated

Abstract

State-of-the-art branch-and-bound algorithms for the maximum clique problem (Maxclique) frequently use an upper bound based on a partition P of a graph into independent sets for a maximum clique of the graph, which cannot be very tight for imperfect graphs. In this paper we propose a new encoding from Maxclique into MaxSAT and use MaxSAT technology to improve the upper bound based on the partition P. In this way, the strength of specific algorithms for Max-clique in partitioning a graph and the strength of MaxSAT technology in propositional reasoning are naturally combined to solve Maxclique. Experimental results show that the approach is very effective on hard random graphs and on DI-MACS Maxclique benchmarks, and allows to close an open DIMACS problem.
BibTeX
@inproceedings{li2010efficient,
  author = {Chu Min Li and Zhe Quan},
  title = {{An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  url = {https://openreview.net/forum?id=S1bGO1-_WB},
}
Figure