Finding a maximum clique given a graph colouring I have some large undirected graphs with $n \approx 10000$ vertices in which I want to find a maximum clique (a clique with greatest number of vertices), and for each of these graphs I have explicit colourings with 26 colours (so that no two adjacent vertices have the same colour). Naturally, this means that the largest clique has at most 26 vertices, but simply iterating over all $\binom{n}{26} \approx n^{26}/26!$ is still too slow computationally. I've been using some implementations of the Bron-Kerbosch algorithm, but it iterates over all maximal cliques, doesn't make use of the colouring, and is too slow.
What are the best algorithms for finding a maximum clique given an explicit colouring, and are there any implementations of these algorithms I can use? The edge density for these graphs is about 76%, and most of the vertices have roughly the same degree. Bonus points if these algorithms are parallelisable.
 A: One can state your question as follows:
Given $k$-partite graph, can we find a $k$-clique in it efficiently?
(Or more efficiently than in general graph).
Note that the coloring defines the partition.
The answer is no, as the following answer shows:

This should be indeed NP-hard. And the construction is very similar to one that already worked for a similar question: https://cstheory.stackexchange.com/questions/30605/many-one-reduction-from-inequality-problem-to-equality-problem.
From a graph $G=(V,E)$ and $k$ construct the graph $G'$ with vertex set $V \times \{1,\dots,k\}$ and edges between $(v,i)$ and $(w,j)$ if $(i \ne j)$ and $(v \ne w)$ and $(v,w) \in E$. It is easy to see that $G'$ is $k$-partite and it has a $k$-clique if and only if $G$ has.

link to the answer.
Two extra comments:

*

*You might be interested in searching for a fast implementation of a small maximal clique detection algorithm.

*Some speedup might be obtained by going over all tuples of $26$ vertices of different colors, other than all tuples of general $26$ vertices in the graph.

A: I don't think that the maximal clique problem can be solved exactly on many graphs with 10000 vertices, but if it is sparse, you can give it a try.
There are standard algorithms like Cliquer or Bron-Kerbosch, but indeed they don't use the given vertex-colouring.
But actually, the 'classical' branch-and-bound algorithm can be enhanced if you have a good vertex-colouring:
The basic idea is to do backtracking over all cliques in increasing order: in each recursive step you have a current clique $C$ and a 'search set' $X$ of vertices which are neighbours of each vertex in $C$. For each $v \in C$ we then go on recursively on $C\cup x$ with the apropriate search set.

This procedure would effectively find all maximal cliques, but if we are only interested in maximum cliques, it can be enchanced with a bounding criterium: if we currently have the clique $C$, and search set $X$, then we backtrack if $|C|+|X|\leq current\_best\_clique$, because it is impossible to find a maximum clique in this way. Furthermore, if we have also have a colouring $c$ then we can backtrack if $|C|+|c(X)| \leq current\_best\_clique$, because the chromatic number is an upper bound for the clique number. (Here $c(X) = \{c(x)\ | \ x\in X\}$)
Also, this branch-and-bound algorithm is quite easy to parallelize. Since it just a large recursion tree, you can 'split' the tree at a certain depth, and distribute the states to different cores, which can operate (almost) completely independently.
All of this should be quite straightforward to implement. The only problem I see is that for finding cliques, I would make heavy use of bitwise operations to compute the common neighbours of the vertices; but this is rather impossible if the graphs have 10000 vertices.
