CS180 Homework 8

CS180 Homework 8

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.)
2. 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
G
0
contains an independent set of size at least k
0
. We proved in class that the Clique problem is
NP-complete. Show that the independent set problem is same by reduction from Clique problem.
3. 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 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 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).
4. 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