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

COMP3027/COMP3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 9 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 you prove that a problem is NP-complete?
Tutorial
Problem 1
The input to the set cover problem is a collection of subsets S1,S2,,Sm of some universal set U, and a number t. The problem is to determine if there are t sets Si1,Si2,,Sit whose union equals U; that is, tj=1Sij =U.
1. Prove that the set cover problem is NP-hard.
2. Argue why the Set Cover problem is more general than the Vertex Cover problem.
Problem 2
Prove that Clique is NP-complete by using a reduction from 3-SAT.
Problem 3
In the Partition problem, we are given a set S of non-negative 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. In the Subset-Sum problem, we are given a set S of integers (possibly negative) and a target integer k (possibly negative), and we need to decide whether there is a subset S of S whose sum equals k. The Subset-Sum problem is known to be NP-hard.
1. Show that the Partition problem is NP-complete. For the NP-hardness proof, give a Karp reduction from the Subset-Sum problem.
1

2. Show that the Knapsack Decision problem is NP-complete. For the NP-hardness proof, give a Karp reduction from the Partition problem.
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 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 6
[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