Incremental Upper Bound for the Maximum Clique Problem

Chu-Min Li (), Zhiwen Fang (), Hua Jiang () and Ke Xu ()
Additional contact information
Chu-Min Li: School of Computer Science, Huazhong University of Science and Technology (HUST), Wuhan 430073, China; Modélisation, Information and Systèmes (MIS), EA 4290, Université de Picardie Jules Verne, Amiens 80000, France
Zhiwen Fang: Modélisation, Information and Systèmes (MIS), EA 4290, Université de Picardie Jules Verne, Amiens 80000, France; State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China
Hua Jiang: School of Computer Science, Huazhong University of Science and Technology (HUST), Wuhan 430073, China
Ke Xu: State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China

INFORMS Journal on Computing, 2018, vol. 30, issue 1, 137-153

Abstract: The maximum clique problem (MaxClique for short) consists of searching for a maximum complete subgraph in a graph. A branch-and-bound (BnB) MaxClique algorithm computes an upper bound of the number of vertices of a maximum clique at every search tree node, to prune the subtree rooted at the node. Existing upper bounds are usually computed from scratch at every search tree node. In this paper, we define an incremental upper bound, called IncUB, which is derived efficiently from previous searches instead of from scratch. Then, we describe a new BnB MaxClique algorithm, called IncMC2, which uses graph coloring and MaxSAT reasoning to filter out the vertices that do not need to be branched on, and uses IncUB to prune the remaining branches. Our experimental results show that IncMC2 is significantly faster than algorithms such as BBMC and IncMaxCLQ. Finally, we carry out experiments to provide evidence that the performance of IncMC2 is due to IncUB.

Keywords: MaxClique; MaxSAT; incremental upper bound (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0770 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:1:p:137-153

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().