# Implementing Nesetril and Poljak's clique detection algorithm

I want to implement the clique detection algorithm by Nesetril and Poljak described in [1].

However, I can't seem to understand how the auxiliary graph $H$ is to be created and how it can be used to detect a clique. For instance, the paper suggests that to detect a clique of size $3\ell$ in a graph of size $n$, we construct an auxiliary graph $H$ of size $n^\ell$. For the detection of a clique of size $6$ in a graph $G$ of size $8$ for example, then the size of $H$ would be $64$ (i.e. $8^2$) and then checking for the presence of a triangle in $H$ which would indicate the presence of a clique of size $6$ in $G$.

Further down, while describing how to construct $H$, they stated that the vertex set of $H$ should be a subset of the vertices of $G$, and that the size of this subset is $\ell$. This is the first conflict. The second conflict is in the construction of the edge set. What is meant by $Y'$ in this sentence: $E(H)=\{ \{Y,Y'\} ; Y \neq Y' \text{ and } Y \cup Y' \text{ forms a complete subgraph in } G \}.$

The paper did not at any point after this sentence define what $Y'$ was.

Any explanation will be appreciated.

The high-level idea is this: the existence of a triangle in $H$ corresponds to the existence of a clique of size $3\ell$ in $G$, and we know how to detect triangles using matrix multiplication.
So let $\ell$ indeed be divisible by three. The auxiliary graph $H$ has a vertex for every $K_\ell$, and an edge between two vertices precisely when the corresponding vertices form a $K_{2\ell}$. Then $G$ has a $K_{3\ell}$ iff $H$ contains a triangle.
Example: Suppose we wish to find cliques of size 6 from a given graph $G$. The trivial algorithm that checks all 6-sets of $V(G)$ runs in time $\Theta(n^6)$. Let's see how we can improve on this.
Observe that $\ell = 2$, i.e., we are looking for cliques of size $3\ell = 6$. To build $V(H)$, we check all 2-sets in $O(n^2)$ time (but of course now the $K_2$'s are precisely the edges of $G$). Similarly to build $E(H)$, we spend $O(n^4)$ time. The graph $H$ has $\Theta(n^\ell)$ vertices, so a triangle can be detected in time $O(n^{\omega \cdot \ell})$ in it, where $\omega < 2.376$ is the exponent of matrix multiplication. In our case, this simplifies to $O(n^{4.752})$ time, beating the naive brute-force algorithm above.
• @chygoz2 I think you got it. Indeed, it's not hard to see there will be several edges added to $H$. For instance, let $G$ be a $K_6$, and consider some $K_4$ in it, say $\{ 1,2,4,5 \}$: there will be (among others) the vertices $12$, $45$, $14$, $25$, $15$, and $24$ in $H$. There are now multiple ways to form $\{1,2,3,4\}$, namely, $12,45$; $14,25$; and $15, 24$. Does it make sense? – Juho Aug 2 '16 at 16:37