COMP3027/COMP3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 10 School of Computer Science
Pre-tutorial questions
Note: Problems 2 and 4 are new this week.
Do you know the basic concepts of this week’s 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) What’s the definition of the class P? (b) What’s 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) What’s the definition of the class NP-complete? 3. How do you prove that a problem is NP-complete?
Tutorial
Problem 1
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.
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 = L∪R (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
1
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 4
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 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