Overall and Delay Complexity of the CLIQUES and Bron-Kerbosch Algorithms

摘要

We revisit the maximal clique enumeration algorithm CLIQUES by Tomita et al. that appeared in Theoretical Computer Science 2006. It is known to work in O(3~(n/3))-time in the worst-case for an n-vertex graph. In this paper, we extend the time-complexity analysis with respect to the maximum size and the number of maximal cliques, and to its delay, solving issues that were left as open problems since the original paper. In particular, we prove that CLIQUES does not have polynomial delay, unless P = NP, and that this remains true for any possible pivoting strategy, for both CLIQUES and Bron-Kerbosch. As these algorithms are widely used and regarded as fast "in practice", we are interested in observing their practical behavior: we run an evaluation of CLIQUES and three Bron-Kerbosch variants on over 130 real-world and synthetic graphs, and observe how their performance seems far from its theoretical worst-case behavior in terms of both total time and delay.