12.6. The Clique Problem

Cliques

---

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 G₁ has vertices

and its edges are

We saw that {2, 4, 6, 8} is an independent set in G₁, which means that {2, 4, 6, 8} is a clique in G₁. But what about a clique in G₁?

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

But look at graph G₂ with vertices {1, 2, 3, 4, 5, 6, 7, 8} and edges

Does G₂ 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 G₂.

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

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:

Iteration 5. There are 4 vertices left, and they all have degree 3. Stop. We have found a clique of G₂ 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 S ⊆ V.

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.

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

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