Implementing Nesetril and Poljak's clique detection algorithm

Question

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.

---

[1] J. Nešetril, S. Poljak, On the complexity of the subgraph problem, Comment.Math. Univ. Carolinae 14 (1985) 415–419.

Answer 1

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.