Question

Descnihe uhot io meant Polyneninl NP-complete pro bkm t amguey wit time reduction another Illustate us cligue proten P Vetex Coves pain of NPC Probems anng en o ther

Answer 1

First let's understand what is polynomial time reduction. Suppose that we can solve problem X in polynomial time. Assume that X can be solved in polynomial time directly to some model of computation. Suppose we had a black box that could solve instances of a problem X; if we write down the input for an instance of X, then in a single step, the black box will return the correct yes/no answer. Now think whether arbitrary instances of problem Y can be solved using a polynomial number of standard computational steps, plus a polynomial number of calls to a black box that solves problem X? If the answer to this question is yes, then we write Y ≤P X; we read this as “Y is polynomial time reducible to X,” or “X is at least as hard as Y (with respect to polynomial time).

Suppose Y ≤P X and there actually exists a polynomial-time algorithm to solve X. Then our specialized black box for X is can be replaced with a polynomial-time algorithm for X. Consider what happens to our algorithm for problem Y that involved a polynomial number of steps plus a polynomial number of calls to the black box. It now becomes an algorithm that involves a polynomial number of steps, plus a polynomial number of calls to a subroutine that runs in polynomial time; in other words, it has become a polynomial-time algorithm.

So if we are able to find solution to one NP Complete problem, we can easily polynomial reduce other NP complete problem into solved one and find algorithm for other NP Complete problem. It means finding polynomial algorithm for one NP Complete problem will eventually find algorithm for all NP Complete problems.

Also, If Y is an NP-complete problem, and X is a problem in N P with the property that Y ≤P X, then X is NP-complete

Proof: Clique Problem ≤P Vertex Cover

The clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.

Vertex Cover Problem: Given a graph G(V, E) and a positive integer k, the problem is to find whether there is a subset V’ of vertices of size at most k, such that every edge in the graph is connected to some vertex in V’.

Here, we consider the problem of finding out whether there is a clique of size k in the given graph. Therefore, an instance of the clique problem is a graph G (V, E) and a non-negative integer k, and we need to check for the existence of a clique of
size k in G.

Now, we need to show that any instance (G, k) of the Clique problem can be reduced to an instance of the vertex cover problem. Consider the graph G’ which consists of all edges not in G, but in the complete graph using all vertices in G. Let us call this the complement of G. Now, the problem of finding whether a clique of size k exists in the graph G is the same as the problem of finding whether there is a vertex cover of size |V| – k in G’. We need to show that this is indeed the case.

Assume that there is a clique of size k in G. Let the set of vertices in the clique be V’. This means |V’| = k. In the complement graph G’, let us pick any edge (u, v). Then at least one of u or v must be in the set V – V’. This is because, if both u and v were from the set V’, then the edge (u, v) would belong to V’, which, in turn would mean that the edge (u, v) is in G. This is not possible since (u, v) is not in G. Thus, all edges in G’ are covered by vertices in the set V – V’.

Now assume that there is a vertex cover V’’ of size |V| – k in G’. This means that all edges in G’ are connected to some vertex in V’’. As a result, if we pick any edge (u, v) from G’, both of them cannot be outside the set V’’. This means, all
edges (u, v) such that both u and v are outside the set V’’ are in G, i.e., these edges constitute a clique of size k.

Thus, we can say that there is a clique of size k in graph G if and only if there is a vertex cover of size |V| – k in G’, and hence, any instance of the clique problem can be reduced to an instance of the vertex cover problem.

To understand the proof, consider the following example graph and its complement:

V' ={A, B, C, D} V" ={E, F}