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

Authors

  • Chu-Min Li Huazhong University of Science and Technology
  • Zhe Quan University of Picardie Jules Verne

DOI:

https://doi.org/10.1609/aaai.v24i1.7536

Keywords:

Branch-and-Bound, Maxclique, MaxSAT, Exact Algorithm for Maxclique

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.

Downloads

Published

2010-07-03

How to Cite

Li, C.-M., & Quan, Z. (2010). An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 128-133. https://doi.org/10.1609/aaai.v24i1.7536

Issue

Section

Constraints, Satisfiability, and Search