# Implementing Nesetril and Poljak's clique detection algorithm

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

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?