12.6. The Clique Problem


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

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 G1 has vertices

{1, 2, 3, 4, 5, 6, 7, 8, 9}

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 G1, which means that {2, 4, 6, 8} is a clique in G1. But what about a clique in G1?

A largest clique in G1 is {1,2}, having just two vertices.

But look at graph G2 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 G2 have a clique of size 3? Yes: {1, 7, 8}. But what about a clique of size 4?

An idea for finding large cliques

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:

  1. Suppose that G has n vertices.

  2. Find a vertex v of the smallest possible degree in G.

  3. If the degree of v is n − 1, stop; G is a clique, so the largest clique in G has size n.

  4. 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 G2.

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 G2 of size 4.

Does that algorithm work? Is it guaranteed to find the largest possible clique?

The complement of a graph

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.

The relationship between cliques and independent sets

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 SV.

Theorem. S is an independent set of G if and only if S is a clique in G.

The Clique problem is NP-Complete

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.

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.

  1. 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.

  2. 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