Consider the clique problem, further discussed in Section 
:
Figure: A small graph with a five-vertex clique
Input: A graph G=(V,E) and integer 
.
Output: Does the graph contain a clique of j vertices; i.e. is there
a subset 
, where 
, such that every pair of vertices in S
defines an edge of G?
For example, the graph in Figure contains a
clique of five vertices.
In the independent set problem, we looked for a subset S with
no edges between two vertices of S.
However, for a
clique, we insist that there always be an edge between two vertices.
A reduction between these problems results by reversing the roles
of edges and
non-edges, an operation known as complementing the graph:
IndependentSet(G,k)
Construct a graph G=(V',E') where V'=V, and
For all (i,j) not in E, add (i,j) to E'
Return the answer to Clique(G',k)
These last two reductions provide a chain linking three different problems. The hardness of clique is implied by the hardness of independent set, which is implied by the hardness of vertex cover. By constructing reductions in a chain, we link together pairs of problems in implications of hardness. Our work is done as soon as all these chains begin with a single problem that is accepted as hard. Satisfiability is the problem that serves as the first link in this chain.