next up previous contents index CD CD Algorithms
Next: Satisfiability Up: Simple Reductions Previous: Independent Set and Vertex

Clique and Independent Set


Consider the clique problem, further discussed in Section gif:

Figure: A small graph with a five-vertex clique  

Input: A graph G=(V,E) and integer tex2html_wrap_inline26073 .

Output: Does the graph contain a clique of j vertices; i.e. is there a subset tex2html_wrap_inline26075 , where tex2html_wrap_inline26077 , such that every pair of vertices in S defines an edge of G? For example, the graph in Figure gif 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:  


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.

Mon Jun 2 23:33:50 EDT 1997