Description

Neel Gupta
Problem 1. 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-approximation 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 the maximum independent set.
Answer:
(a) True. If Ham-Cycle, which a known NP-Complete problem, were polynomial time reducible to interval schedule, a question with a polynomial time solution, it would then imply P = NP.
(b) False. The 3-SAT problem is a famous NP-Complete problem and is a decision problem, and decision problems are at least as hard as other problems in NP-Hard.
(c) False. The 0/1 Knapsack problem has a pseudo-polynomial runtime algorithm, but this does not imply that the problem is NP-Hard.
(d) False. An approximation algorithm would only provide a solution for the TSP problem and does not imply anything about the 3-SAT problem.
(e) True. A vertex belonging to a minimum vertex cover is, by definition, not part of the maximum independent set, as they are complements of each other.
Problem 2. Given an undirected graph with positive edge weights, the BIG-HAM-CYCLE problem is to decide if it contains a Hamiltonian cycle C such that the sum of the weights of the edges in C is at least of the total sum of weights of edges in the graph. Show that finding BIG-HAMCYCLE in a graph is NP-Complete.
Answer:
We want to first show that BIG-HAM-CYCLE is in NP, then we want to show that it is NP-hard.
Given a graph G = (V, E) with edge weights w(e), we can verify in polynomial time whether a given cycle C is a valid Hamiltonian cycle and if the sum of edge weights in C is at least half of the total sum of edge weights in the graph. We can check that every vertex in V is visited exactly once in C and that the sum of weights in C is at least . Thus, the BIG-HAM-CYCLE problem is in NP.
To show that BIG-HAM-CYCLE is NP-hard, we will reduce the Hamiltonian Cycle Problem (HAM-CYCLE), a known NP-hard problem, to the BIG-HAM-CYCLE problem. The reduction should be able to be computed within polynomial time.
Given an instance of the HAM-CYCLE problem with a graph G =
(V, E), we will construct a graph G′ for the BIG-HAM-CYCLE problem as follows:
1. Keep the same graph with the same vertices and edges.
2. Assign each edge a weight of 1.
Now, we can show that G has a Hamiltonian cycle if and only if G′ has a BIG-HAM-CYCLE.
Forward: Suppose G has a Hamiltonian cycle H. The corresponding cycle in G′ with the same edges as H will have a total weight of |V|. As the sum of all edge weights in G′ is equal to the number of edges (|E|) and |V| ≤ |E|, this cycle is a valid BIG-HAM-CYCLE in G′.
Backward: Suppose G′ has a BIG-HAM-CYCLE C. Since the cycle visits all vertices and has a total weight of at least half the total sum of weights in the graph, it must be a Hamiltonian cycle in the original graph G.
Therefore, the BIG-HAM-CYCLE problem is NP-Complete since it is in NP and at least as hard as another NP-hard problem.
Problem 3. Given an undirected connected graph G = (V, E) in which a certain number of tokens t(v) = 1, 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 the 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.
Answer:
We reduce Hamiltonian Path (HP) to the token game problem to show it is in NP-hard. Given a HP instance with graph G = (V, E), construct a token game instance as follows:
1. For v ∈ V, set t(v) = 2.
2. For (u, v) ∈ E, add vertex wu,v with t(wu,v) = 1, and edges (u, wu,v),
(wu,v, v).
Forward: Given HP P in G, construct a sequence of moves:
1. For v ∈ V, remove 2 tokens from v, add 1 token to the adjacent vertex in P.
2. For wu,v in P, remove 2 tokens from wu,v, add 1 token to the adjacent vertex in P.
One token remains, so Hamiltonian Path implies a valid sequence.
Backward: Given a valid sequence with one token remaining, since the initial total tokens is 2|V| + |E| and each move decreases tokens by 1, the number of moves is 2|V| + |E| − 1.
Since each v ∈ V must be involved in a move (initially 2 tokens), there must be a path visiting every vertex exactly once, a Hamiltonian Path. Thus, the token game problem is NP-hard.
Problem 4. 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 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.
Answer:
We will prove the Redundant Clubs problem is NP-Complete by first showing that it is in NP then reducing it to the Set Cover problem, a known NP-hard problem, to the Redundant Clubs problem. The reduction should be able to be computed within polynomial time.
To show that the Redundant Clubs problem is in NP, we can verify in polynomial time that, given a set of K clubs to disband, every person still belongs to at least one club.
Given an instance of the Set Cover problem with a universe U, a collection of sets S, and an integer k, we will construct an instance of the Redundant Clubs problem as follows:
1. People: U
2. Clubs: S
3. Membership: person u ∈ U belongs to clubs corresponding to the sets containing u in S.
4. Set K = |S| − k.
Now, we can show that there exists a set cover of size k in the Set Cover instance if and only if there exists a set of K clubs to disband in the Redundant Clubs instance, leaving everyone with at least one club membership.
Forward: Given a set cover S′ of size k, disband clubs in S − S′. Each person in U belongs to at least one set in S′, so everyone still has at least one club membership.
Backward: Given a set of K clubs to disband, the remaining clubs form a set cover of size k in the Set Cover instance. All people in U have membership in at least one club, corresponding to the sets in S that cover the universe U.
Since the Redundant Clubs problem is in NP and we have shown a polynomial-time reduction from the Set Cover problem, which is NP-hard, the Redundant Clubs problem is NP-Complete.
Problem 5. 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.
Answer:
To prove that HALF-IS is NP-Complete, we first show that it is in NP and then show that it is NP-hard by reducing the Independent Set problem, a known NP-hard problem, to HALF-IS.
Given a graph G = (V, E) and a subset V′ ⊆ V with size , we can verify in polynomial time whether V′ is an independent set by checking that no pair of vertices in V′ share an edge. Therefore, HALF-IS is in NP.
Reduction from Independent Set to HALF-IS: Given an Independent
Set instance with a graph G′ = (V′, E′) and an integer k, construct a graph G = (V, E) as follows:
1. Include all vertices and edges from G′ in G.
2. Add a new set of isolated vertices I to G, with size |V′| − 2k.
3. Set V = V′ ∪ I.
Now, we can show that the Independent Set instance has an independent set of size k if and only if the graph G has an independent set of size
.
Forward: Given an independent set A of size k in G′, construct an independent set B in G by including all vertices from A and all isolated vertices from I. The size of B is k , and since no vertices in I are connected to any other vertices, B is an independent set.
Backward: Given an independent set B of size in G, remove all vertices from I to obtain an independent set A in G′. Since k +(|V′| − 2k), the size of A is k. Thus, G′ has an independent set of size k.
Since HALF-IS is in NP and we have shown a polynomial-time reduction from the NP-hard Independent Set problem, HALF-IS is NP-Complete.