Finding Maximum k-Cliques Faster Using Lazy Global Domination

Proceedings of the International Symposium on Combinatorial Search, 9

Volume

Vol. 9 No. 1 (2016): Ninth Annual Symposium on Combinatorial Search

Long Papers

A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem, although large sparse k-clique graphs reduce to large dense clique graphs, which can be computationally challenging. We adapt a state of the art maximum clique algorithm to show that this reduction is in fact useful in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs. We also use thread-parallel search to solve some harder instances.

10.1609/socs.v7i1.18387