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') whereV'=V, andFor all (

i,j) not inE, add (i,j) toE'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.

Mon Jun 2 23:33:50 EDT 1997