Determine if the following statements are true or false.for each statement, briefly explain your reasoning.
(a) If Ham-Cycle is polynomial time reducible to interval scheduling problem then
P = NP.
(b) The NP-Hard class of problems does not contain any decision problems.
(c) If there exists an algorithm that solves problem X with pseudo-polynomial runtime, then X must be NP-Hard.
(d) Suppose there is a 7-approxmiation algorithm for the general Traveling Salesman Problem. Then there exists a polynomial time solution for the 3-SAT problem.
(e) A vertex that is part of a minimum vertex cover can never be a part of a maximum independent set.
2. (15pts) Given an undirected graph with positive edge weights, the BIGHAM- CYCLE problem is to decide if it contains a Hamiltonian cycle C such that the sum of weights of edges in C is at least half of the total sum of weights of edges in the graph. Show that finding BIG-HAM-CYCLE in a graph is NP-Complete.
3. (15pts) Given an undirected connected graph G= (V, E) in which a certain number of tokens t(v) = 1 or 2 placed on each vertex v. You will now play the following game. You pick a vertex u that contains at least two tokens, remove two tokens from u and add one token to any one of adjacent vertices. The objective of the game is to perform a sequence of moves such that you are left with exactly one token in the whole graph. You are not allowed to pick a vertex with 0 or 1 token. Prove that the problem of finding such a sequence of moves is NP-Hard by reduction from Hamiltonian Path.
4. (20 pts) In a certain town, there are many clubs, and every adult belongs to at least one club. The town’s people would like to simplify their social life by disbanding as many clubs as possible, but they want to make sure that afterwards everyone will
1
still belong to at least one club. Formally the Redundant Clubs problem has the following input and output. INPUT: List of people; list of clubs; list of members of each club; number K. OUTPUT: Yes if there exists a set of K clubs such that, after disbanding all clubs in this set, each person still belongs to at least one club. No otherwise. Prove that the Redundant Clubs problem is NP -Complete.
5. (15 pts) Given a graph G=(V, E) with an even number of vertices as the input, the
HALF-IS problem is to decide if G has an independent set of size . Prove that HALF-IS is in NP-Complete.
2
