Question

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether G contains a clique of size m or more. (A clique of size k in a graph is its complete subgraph of k vertices.)

Determine, for a given graph G = V,E and a positive integer m ≤ |V |, whether there is a vertex cover of size m or less for G. (A vertex cover of size k for a graph G = V,E is a subset V⊆ V such that |V| = k and, for each edge (u, v) ∈ E, at least one of u and v belongs to V.)

a.)Describe the process of showing that a problem is NP complete

b.) given that the CLIQUE problem is NP complete. show that the VERTEX COVER problem is NP complete.

Answer 1

Answer a

A problem Y can be shown as NP-Complete. If

1. Y belongs to NP problems. Prove Y NP
2. There is a problem X which is NP Complete and can be polynomial reducible to Y.  X Y

Answer b

Prove that Vertex Cover is NP problem.

We know that vertex cover of any undirected graph G = (V, E) is a subset of vertices V' such that if (u, v) E then either u V' or v V' or both (u, v) V'

For example, in the following graph all edged can be covered by minimum two vertices either {b, c} or {a, c} so this will be vertex cover for graph below. Vertex Cover Size k = 2

Now, we can see that a problem is called NP when any solution of that can be verified in polynomial time. We know that vertex cover can not be solved in polynomial time but this solution of vertex cover {b, c} can be easily verified in polynomial time. vertex b covers the edge a-b and vertex c covers remaining 3 edges which is easily verifiable in polynomial time. So we can say that

Vertex Cover NP

Prove that Clique Problem can be polynomial reducible to Vertex Cover Problem.

Instance of Clique => Polynomial Reduction => Instance of Vertex Cover => Polynomial verifiable

We know that Clique of any graph G is sub-graph G' which is complete graph means each vertex in the sub-graph is connected to other vertices of sub-graph.

For example, in graph below Clique V' = {a, b, c, d}. Clique Size k = 4

Now let's try to find G' of graph G using some reduction algorithm. G' is graph with vertices V G and Edged E which are not present in complete graph of G. It means if we consider G as a complete graph the edges which are missing in graph G will be part of G'.

Here we can see that vertex cover of graph above V' = {e, f}

So conversely we can say that if there is a graph G' which has vertex cover as V' of size |V| - k where V' is subset of V of Graph G and k is clique size. So we can say that G has a vertex cover of size k if and only if G' has a clique of size |v| - k. This can also be verified in polynomial time.