Suppose that G is an undirected graph. Say that a set S of vertices of G form a clique if each vertex in S is adjacent to each other vertex in S.
The clique problem is as follows.
Input. An undirected graph G and a positive integer K.
Question. Does G have a clique of size at least K?
Let's look at the same example graph that was used earlier for the Vertex Cover and Independent Set problems, where G_{1} has vertices
and its edges are
{1, 2}, | {1, 4}, |
{1, 6}, | {1, 8}, |
{2, 3}, | {3, 4}, |
{4, 5}, | {5, 6}, |
{6, 7}, | {7, 8}, |
{8, 9}, | {2, 9}. |
We saw that {2, 4, 6, 8} is an independent set in G_{1}, which means that {2, 4, 6, 8} is a clique in G_{1}. But what about a clique in G_{1}?
A largest clique in G_{1} is {1,2}, having just two vertices.
But look at graph G_{2} with vertices {1, 2, 3, 4, 5, 6, 7, 8} and edges
{1, 2}, | {1, 6}, |
{1, 7}, | {1, 8}, |
{2, 3}, | {2, 5}, |
{2, 6}, | {3, 5}, |
{3, 6}, | {4, 5}, |
{4, 6}, | {5, 6}, |
{7, 8}. |
Does G_{2} have a clique of size 3? Yes: {1, 7, 8}. But what about a clique of size 4?
Here is an idea for finding a large clique.
The degree of a vertex v is the number of edges that are connected to v.
To find a clique of G:
Suppose that G has n vertices.
Find a vertex v of the smallest possible degree in G.
If the degree of v is n − 1, stop; G is a clique, so the largest clique in G has size n.
Otherwise, remove v and all of its edges from G. Find the largest clique in the smaller graph. Report that as the largest clique in G.
Let's run this algorithm on G_{2}.
Iteration 1. Vertex 7 has degree 2. Remove it.
Iteration 2. After removing vertex 7, vertex 8 has degree 1. Remove it. The remaining graph has vertices {1, 2, 3, 4, 5, 6} and edges
{1, 2}, | {1, 6}, |
{2, 3}, | {2, 5}, |
{2, 6}, | {3, 5}, |
{3, 6}, | {4, 5}, |
{4, 6}, | {5, 6}. |
Iterations 3 and 4. Vertices 1 and 4 each have degree 2. They are removed. Now the vertices are {2, 3, 5, 6} and the edges are:
{2, 3}, | {2, 5}, |
{2, 6}, | {3, 5}, |
{3, 6}, | {5, 6}. |
Iteration 5. There are 4 vertices left, and they all have degree 3. Stop. We have found a clique of G_{2} of size 4.
Does that algorithm work? Is it guaranteed to find the largest possible clique?
An undirected graph is described by a pair (V, E) where V is set of vertices and E, the set of edges, is a set of two-element subsets of V.
If G = (V, E) is an undirected graph, define G = (V, E). That is,
{u,v} is an edge of G if and only if {u,v} is not an edge of G.
Notice that a clique is concerned with the presence of edges between all members of a set of vertices, while an independent set is concerned with the absence of edges between those members.
The following should be obvious.
Let G = (V,E) by an undirected graph and suppose S ⊆ V.
Theorem. S is an independent set of G if and only if S is a clique in G.
The algorithm above does not work. You can find a counterexample, where the algorithm removes a vertex that is part of the largest clique, but here is a simple observation.
We will show that the Clique problem is NP-complete.
It is easy to see that the algorithm above is a polynomial-time algorithm.
Putting those facts together, if the algorithm above works, then P = NP.
Theorem. The Clique problem is NP-complete.
Proof. Lets use abbreviation CP for the Clique problem. IS is the Independent Set problem.
It suffices to show (a) the clique problem is in NP, and (b) IS ≤_{p} CP.
Part (a) is easy. We need to find a nondeterministic polynomial-time algorithm for CP.
Pair (G, K) is in CP if there exists a set of vertices S of size at least K so that for every pair of vertices u and v in S, {u,v} is an edge in G.
The evidence is a set of vertices S of size at least K. The evidence is accepted if {u,v} is an edge in G, for every pair of vertices u, v in S.
Part (b) is also easy. Define f(G, K) = (G, K). Then
(G,K) ∈ IS | ⇔ | G has an independent set of size at least K |
⇔ | G has a clique of size at least K | |
⇔ | (G, K) ∈ CP |