[SOLVED] CS algorithm COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 11 School of Computer Science

COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 11 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this weeks lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Reduction.
(a) What is a polynomial-time reduction?
(b) What is the difference between a Cook reduction and a Karp reduction?
(c) Are polynomial-time reductions transitive?
(d) What are the three types of standard reductions?
2. Classes
(a) Whats the definition of the class P? (b) Whats the definition of the class NP?
(c) Is it known if P=NP?
(d) How do you prove that a problem is in NP?
(e) Whats the definition of the class NP-complete? 3. How do one prove that a problem is NP-complete?
Tutorial
Problem 1
In the Partition problem, we are given a set S of integers, and we need to decide whether there is a partition of S into two subsets S1 and S2 such that the sum of S1 equals the sum of S2. Note that each integer of S has to belong in exactly one of S1 and S2.
1. Show that the Partition problem is NP-complete. For the NP-hardness proof, give a Karp reduction from the Subset-Sum problem.
2. Show that the Knapsack Decision problem is NP-complete. For the NP-hardness proof, give a Karp reduction from the Partition problem.
Problem 2
In the Bipartite Covering problem, we are given a bipartite graph G = (V,E), where V = LR (L and R are the left and right vertices, respectively), and an integer k. The problem is to decide if there exists a subset L of L of size k such that every vertex in R has a neighbor in L. Show that this problem is NP-complete.
Problem 3
In the Degree Spanning Tree problem we are given a graph G = (V,E) and we have to decide whether there is a spanning tree of G whose maximum degree is at most . (Note that is not part of the input, but rather part of the problem definition.) It is known that the Degree 2 Spanning Tree problem (D2ST)
1

is NP-complete. Using this fact, prove that Degree Spanning Tree is NP-complete for all fixed > 2 (DST).
Problem 4
Given a graph G = (V,E), a subset of vertices X and a number k, the Steiner Tree problem is to decide whether there is a set S V of size at most k such that G[X S] is connected. Consider the following reduction from 3-SAT to the Steiner Tree problem.
Let = C1 Cm be a boolean formula over variables x1,,xn such that each clause Ci is the disjunction of three literals. We define a graph G = (V, E) and a target k based on :
1. For each clause Ci we create a vertex ui X; for each variable xj we create two vertices vjT and vjF that belong to V X. Finally, we add a dummy node d X.
2. For each clause Ci, if Ci contains the literal xj then we create the edge (ui,vjT), while if Ci contains the literal xj then we create the edge (ui , vjF ). Finally, we connect d to every vjT and vjF .
3. Wesetthetargetktoben.
Prove that the reduction is broken. That is, show a Yes instance being mapped to a No instance or
vice versa.
Problem 5
Given a graph G = (V,E), a distinguished subset of vertices X V and a number k, the Steiner Tree problem is to decide whether there is a set S V of size at most k such that G[X S] is connected.
Prove that this problem is NP-complete.
Problem 6
Given a directed graph G = (V, E) a feedback set is a set X V with the property that G X is acyclic. The Feedback Set problem asks: Given G and k, does G have a feedback set of size at most k? Prove Feedback Set P Set Cover.
Problem 7
Prove that Clique is NP-complete by using a reduction from 3-SAT.
Problem 8
[Advanced] In this tutorial problem, we will show a simple equivalence between the vertex cover problem and the maximum matching problem in bipartite graphs. Let G = (V, E) be a bipartite graph with n vertices on each side, and let C be the size of the minimum vertex cover and M be the size of the maximum matching.
1. Show that C M.
2. Show that C M.
3. Conclude that on bipartite graphs, the Vertex Cover, Independent Set and Clique problems admit polynomial-time algorithms.
4. Give an example of a non-bipartite graph where the minimum vertex cover is larger than the maximum matching.
2