A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments

Etsuji TOMITA  Yoichi SUTANI  Takanori HIGASHI  Mitsuo WAKATSUKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D    No.6    pp.1286-1298
Publication Date: 2013/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1286
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
maximum clique,  branch-and-bound,  approximate coloring,  computational experiments,  

Full Text: PDF>>
Buy this Article


Summary: 
Many problems can be formulated as maximum clique problems. Hence, it is highly important to develop algorithms that can find a maximum clique very fast in practice. We propose new approximate coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, pp.95–111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Extensive computational experiments confirm the superiority of MCS over MCR and other existing algorithms. It is faster than the other algorithms by orders of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graph. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs. This paper demonstrates in detail the effectiveness of each new techniques in MCS, as well as the overall contribution.