Clique problem example ppt

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 is an independent set in G₁, which means that is a clique in G ₁. But what about a clique in G₁?

A largest clique in G₁ is , having just two vertices.

But look at graph G₂ with vertices and edges

Does G₂ have a clique of size 3? Yes: . 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 and edges

Iterations 3 and 4. Vertices 1 and 4 each have degree 2. They are removed. Now the vertices are 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.

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.

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

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 Kso 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