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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top