Description
1. Suppose 2n teams play in a roundrobin 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 t_{w} 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 IndependentSet problem asks whether G^{0} contains an independent set of size at least k^{0}. We proved in class that the Clique problem is NPcomplete. 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.
SetCover: Given a collection of sets, and a number k, the SetCover 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.
HittingSet: Given a collection of sets, and a number k, the HittingSet problem asks if are there at most k elements of the sets such that there is at least one element from each set?
DominatingSet: Given an undirected graph G, and a number k, the DominatingSet problem 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 SetCover, HittingSet and DominatingSet are polynomialtime reducible to each other.
(Hint: One strategy is to show SetCover _{p} HittingSet, HittingSet _{p} DominatingSet and DominatingSet _{p} SetCover. An alternative way is to show HittingSet _{p} DominatingSet, DominatingSet _{p} HittingSet, SetCover _{p} DominatingSet and DominatingSet _{p} SetCover. In class we have seen VertexCover reduced poly to DominatingSet).

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 polynomialtime reducible to each other.

Express your algorithm in a wellstructured 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 L^{A}T_{E}X, L_{Y}X or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.
2