Homework 8 Solution

1. Suppose 2n teams play in a round-robin tournament. Over a period of 2n 1 days, every team plays every other team exactly once. There are no ties. Show that for each day we can select a winning team, without selecting the same team twice. (Hint: Consider a bipartite graph with a set of team vertices and a set of day vertices. Take any set of days W and assume not all teams won in some day in W . Let tw be a team that did not win in any day in W . Consider the implication on the number of teams that won at least once in some day in W . Invoke Hall’s Theorem.)




Given an undirected graph G = (V, E) and an integer k. A clique of G is a subset V 0 V of vertices, each pair of which is connected by an edge in E. The Clique problem asks whether G contains a clique of size at least k. An independent set of G is a subset V 0 V of vertices such that each edge in E is incident on at most one vertex in V 0. The Independent-Set problem asks whether G0 contains an independent set of size at least k0. We proved in class that the Clique problem is NP-complete. Show that the independent set problem is same by reduction from Clique problem.



Show that the following three problems are polynomial time reducible to each other.



Set-Cover: Given a collection of sets, and a number k, the Set-Cover problem asks if there are at most k sets from the collection of sets such that their union contains every element in the union of all sets.




Hitting-Set: Given a collection of sets, and a number k, the Hitting-Set problem asks if are there at most k elements of the sets such that there is at least one element from each set?




Dominating-Set: Given an undirected graph G, and a number k, the Dominating-Set prob-lem asks if there is a subset of vertices of size k such that every vertex in the graph is either in the subset or has a neighbor that is in the subset.




Prove Set-Cover, Hitting-Set and Dominating-Set are polynomial-time reducible to each other.




(Hint: One strategy is to show Set-Cover p Hitting-Set, Hitting-Set p Dominating-Set and Dominating-Set p Set-Cover. An alternative way is to show Hitting-Set p Dominating-Set, Dominating-Set p Hitting-Set, Set-Cover p Dominating-Set and Dominating-Set p Set-Cover. In class we have seen Vertex-Cover reduced poly to Dominating-Set).




Given a directed graph G = (V, E) and a pair of vertices s, t in G, the Hamiltonian Path problem asks whether there is a simple path from s to t that visits every vertex of G exactly once. The Hamiltonian Cycle problem asks if there is a cycle in a directed graph G that visits every vertex exactly once. Show that Hamiltonian Path and Hamiltonian Cycle problems are polynomial-time reducible to each other.












Express your algorithm in a well-structured manner. Use pseudo code and the textbook has good examples to follow. Avoid using a long continuous piece of text to describe your algorithm. Start each problem on a NEW page. Unless specified, you should justify the time complexity of your algorithm and why it works. For grading, we will take into account both the correctness and the clarity. Your answers are supposed to be in a simple and understandable manner and sloppy answers are expected to receiver fewer points.



1



Homework assignments are due on Gradescope. Email attachments or paper submissions are NOT acceptable.



Raw photo is NOT acceptable. Upload your homework as a PDF scan by using a scanner or mobile scanner app. Match each problem with your answer on Gradescope. Use dark pen or pencil and your handwriting should be clear and legible.



We recommend using LATEX, LYX or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.





































































































































































2