Clique Problem (CLIQUE)

The Clique Problem (CLIQUE) takes an input of:

• an undirected graph $G=(V,E)$
• an integer $k>2$

It provides an output of $\top$ if and only if $G$ contains a clique of size $k$.

Clique

A clique is a subset of an undirected graph such that every two distinct vertices in the clique are adjacent.

Link to original