CSCE629- Analysis of Algorithms Assignment 6 Solved

A vertex cover in an undirected graph G is a set C of vertices in G such that every edge in G has at least one end in C. Consider the following two versions of the Vertex-Cover problem:

VC-D: Given a graph G and an integer k, decide whether G contains a vertex cover of at most k vertices.

VC-O: Given a graph G, construct a minimum vertex cover for G

Prove: VC-D is solvable in polynomial time if and only if VC-O is solvable in polynomial time. 2. Prove that the VC-D problem given in Question 1 is in NP.

3. Using the fact that the independent set problem is NP-complete, prove that the following problem is NP-complete:

Clique: Given a graph G and an integer k, is there a set C of k vertices in G such that for every pair v and w of vertices in C, v and w are adjacent in G?

1

Definitions.

1.        P is the collection of all (decision) problems that can be solved in polynomial time. Thus, P is the collection of all “easy” problems.

2.        NP is the collection of all (decision) problems whose solutions, though perhaps not easy to construct, but can be checked in polynomial time. NP contains many problems that are not known to be in P. Examples include traveling salesman, satisfiability, and independent set. Huge amount of efforts has been paid trying to develop polynomial-time algorithms for these problems, but all failed. A common belief is that these problems are hard and do not belong to P, i.e., P6= NP.

3.        Q1 ≤pm Q2 means that up to polynomial-time computation, Q1 is not harder than Q2.

4.        NP-hard problems are those that are not easier than any problems in NP (up to polynomial-time computation). Based on the common belief given in 2, an NP-hard problem cannot be solved in polynomial time.

Some thing you may want to remember.

1.        To show Q1 ≤pm Q2, you need to construct a polynomial-time algorithm that computes a function f such that x is a yes-instance of Q1 if and only if f(x) is a yes-instance of Q2.

2.        To prove that a problem Q is in NP, you need to construct a polynomial-time algorithm A(x,y) such that for any yes-instance x1 of Q, there is a y1 such that A(x1,y1) = 1, and for any no-instance x2 of Q, A(x2,y) = 0 for all y.

3.        To prove that a problem Q is NP-hard, you need to pick a problem Q0 that is known to be NP-hard, and show Q0 ≤pm Q.

4.        To prove that a problem Q is NP-complete, you need to prove both that Q is NP-hard and that Q is in NP.

5.        You should remember of the definitions of at least the following NP-complete problems:

satisfiability, independent set, vertex cover, partition, and subset-sum.