Answer to Question #145484 in Algorithms for Taylor

Question

1. Show that 3-SAT problem is in NP appealing to the definition of the NP class .

2. Finding a vertex cover of a graph, is a problem of finding a set of vertices of minimum size such that each edge in the graph is covered with at least one vertex. Formulate a decision version of the vertex cover problem.

3. Suppose A and B are two different decision problems and furthermore assume that problem A is polynomial-time reducible to problem B. If problem B is NP-complete, is problem A NP-complete ? Justify your answer.

Answer 1

1. If a boolean expression E in CNF is satisfiable, non deterministically guess values for all the variables and then evaluate the expression, E turns out to be true then accept. This carried out in nondeterministic polynomial time, thus 3SAT is in NP.

Approx-Vertex-Cover (G = (V, E))  
{             
       C = empty-set;  
    E'= E;  
    While E' is not empty do  
      {  
    Let (u, v) be any edge in E': (*)  
    Add u and v to C;  
    Remove from E' all edges incident to  
       u or v;  
      }  
    Return C;  
}

3.As per the question, It is given that A and B are two different decision problems, and Problem A is polynomial time many-one reducible to B.

Problem A is NP-complete, then we to prove that problem B is also NP-complete.

As per the definition, a problem B is said to be NP-complete if-

• B is NP
• There exists an NP-complete problem A that reduces to B

Here it is already assumed that problem A is reducible to problem B. So we can say that B is NP-complete.