An enhanced bitstring encoding for exact maximum clique search in sparse graphs

Abstract

This paper describes BBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example is correspondence graphs derived from data association problems. The new algorithm is based on the bit-parallel kernel used by the BBMC family of published exact algorithms. BBMCW employs a new bitstring encoding that we denote ‘watched’, because it is reminiscent of the ‘watched literal’ technique used in satisfiability and other constraint problems. The new encoding reduces the number of spurious operations computed by the BBMC bit-parallel kernel in large sparse graphs. Moreover, BBMCW also improves on bound computation proposed in the literature for bit-parallel solvers. Experimental results show that the new algorithm performs better than prior algorithms over data sets of both real and synthetic sparse graphs. In the real data sets, the improvement in performance averages more than two orders of magnitude with respect to the state-of-the-art exact solver IncMaxCLQ.

Keywords:

• maximum clique
• bitstring
• branch-and-bound
• graph
• combinatorial optimization

Acknowledgements

We would also like to thank Alvaro Lopez for his help in the initial stages of this research.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is sponsored by the Spanish Ministry of Economy and Competitiveness (MINECO) [grant number DPI2014-53525-C3-1-R]. Panos M. Pardalos and Mikhail Batsyn are supported by the Laboratory of Algorithms and Technologies for Network Analysis, NRU HSE [RSF grant 14-41-00039]. This work was supported by the Ministry of Education and Science of the Russian Federation [14-41-00039].