[Solved] CSCE-629 Analysis of Algorithms -Assignment # 6

(The homework is due April 30, at 5:00pm. Please submit it to HRBB 315C)

1. 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. Q₁ ^p_m Q₂ means that up to polynomial-time computation, Q₁ is not harder than Q₂.
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 Q₁ ^p_m Q₂, you need to construct a polynomial-time algorithm that computes a function f such that x is a yes-instance of Q₁ if and only if f(x) is a yes-instance of Q₂.
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 x₁ of Q, there is a y₁ such that A(x₁,y₁) = 1, and for any no-instance x₂ of Q, A(x₂,y) = 0 for all y.
3. To prove that a problem Q is NP-hard, you need to pick a problem Q₀ that is known to be NP-hard, and show Q₀ ^p_m 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.

2