## How to find maximal cliques

Facebook used to have this awesome list of programming puzzles that were freely available. One of them was peak-traffic, which can be rephrased as the maximal cliques problem pretty easily. Unfortunately a graph can have exponential number of maximal cliques, so it's not surprising that we can not find a polynomial algorithm for listing all possible maximal cliques in a graph. However there are output sensitive algorithms: as long as the number of maximal cliques is relatively low each can be reported in a short time.

I knew that I was looking for such an algorithm, but it was kind of hard to find a detailed enough description on the Internet. At the time of writing Wikipedia does provide a short description of the algorithm devised by *Tsukiyama et al.* but there are a number of details omitted, making it kind of hard to come up with the right implementation.

My aim is to provide a simple to understand description of the algorithm (without proof that it works correctly) and share my implementation in C++. (Type `make smoke` to compile and test.) The source I've been using - apart from Wikipedia - was a 2004 paper written by *Kazuhisa Makino* and *Takeaki Uno*: *New Algorithms for Enumerating All Maximal Cliques. *