CSCI570 Homework11 Solution

Q2: The k-cycle-decomposition problem for any k > 1 works as follows. The input consists of a connected graph G=(V, E) and k positive integers a1, …, ak < |V|. The goal is to determine whether there exist k disjoint cycles of sizes a1, …, ak respectively, s.t., each node in V is contained in exactly one cycle. Show that this problem is NP-complete (for any k > 1). (20 pts)
Q3. 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 |V| / 2. Prove that HALF-IS is in
NP-Complete. (20pts)
Ungraded Problems
Q4. 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 closing off as many clubs as possible, but they want to make sure that everyone will still belong to at least one club afterwards.
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 removing all these K clubs, each person still belongs to at least one club. No otherwise.
Prove that the Redundant Clubs problem is NP-Complete. (20pts)
Q5. You are given a directed graph G=(V,E) with weights on its edges e∈E. The weights can be negative or positive. The Zero-Weight-Cycle Problem is to decide if there is a simple cycle in G so that the sum of the edge weights on this cycle is exactly 0. Prove that this problem is NP-complete. (20pts)
Hint: Use the Subset-Sum Problem