Answer Happy

(4 points) Question 4: NP-Completeness [25 Points] (a) Classify the following problems as P, NP-Complete or NP-hard: 1. Fractional Knapsack 2. Finding the minimum weighted distance between two vertices in a graph 3. Vertex Cover in its optimization form 4. 3-Conjuctive Normal Form Satisfiability (3-CNF SAT) (b) What is complexity class NP? (2 points) (c) Under what conditions will a problem be NP-complete? Use the mathematical notation. (2 points) (d) If Problem A is polynomially reducible to Problem B, and B can be solved in polynomial time, what can we conclude about A? (2 points) (e) If Problem A is polynomially reducible to Problem B, and cannot be solved in polynomial time, what can we conclude about A? (2 points) (1) Under what condition will be equal to NP? Briefly explain. (3 points) (9) State the Clique problem described in class in both its optimization form and its decision form. (2 points)

(h) Consider the following two problems: HAM-Cycle: Given an undirected graph, determine if there is a simple cycle that visits all vertices. HAM-Path: Given an undirected graph, determine if there is a simple path that visits all vertices. So, the difference between a cycle and a path is that the cycle has one extra edge that returns to the starting vertex Now, assuming that HAM-Path is known to be NP-complete, we would like to prove that HAM- Cycle is NP-complete 1. Explain why a reduction that simply uses the same graph without any modifications as the input to both solvers will not give a valid proof. (2 points) 2. Give a valid reduction that does a certain modification of the graph to prove the NP- completeness of HAM-Cycle given the NP-completeness of HAM-Path. Clearly describe the modification, and then give logical arguments proving the correctness of the reduction. (Hint: Add an extra vertex]. (6 points)