Maximum Clique using Greedy Vertex Colouring

Maximum Clique and NP-Complete

The maximum clique is an old problem in Computer Science. It is proven that it is indeed NP-Complete. Thus, at best we can find optimised solutions rather than solving it optimally.

Algorithm

Before we start, and after reading the graph, we first enumerate the vertices as keys, and sort them based on the their colour of each vertex.

After that, while there are vertices and there still branches we read the neighbours of each vertex and start a thread branching over the neighbours where for each thread we pick the highest-coloured vertex, most promising to be part of a max clique, and look for all vertices that are adjacent to it in all other neighbours (recursively).

When reaching an empty set of vertices, we backtrack and collect vertices if a maximum clique has been already in that thread, we shall find it if the size of the maximum clique overall has changed during the processing.

Source code

Recently, I have merged a PR into a graph visualisation library called graphonline. It was based on this draft.