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 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 one 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.
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.
1
Solution: (Sketch.)
1. The problem is in NP: the certificate consists of the two subsets S1 and S2, and it is
easy to check in polynomial time that their sums are equal.
Now we prove NP-hardness by a polynomial-time reduction from the Subset-Sum prob- lem. Consider a Subset-Sum instance with integers V = {v1 , . . . , vn } and target value t. Let a = v1 + . . . + vn. Consider the case that t ≤ a/2. The Partition instance consists of the integers S = {v1, . . . , vn, a − 2t}. Note that a − 2t is non-negative by assumption.
Suppose there exists a subset V ′ of V that sum to exactly t. Then, consider the partition of S into sets S1 = V ′ ∪ {a − 2t} and the set S2 = V \ V ′. Both of these sets sum to a−t.
Suppose there exists a partition of S into sets S1 and S2 whose sums are equal. Since the sum of S is 2a−2t, each of S1 and S2 sums to a−t. Suppose S1 is the set that contains a − 2t. Then the remaining integers in S1 belong to V and sum to a − t − (a − 2t) = t. See figure below for an illustration (credit to Alex Stephens).
To handle the case when t > a/2, note that there exists a subset that sums to t if and only there exists a subset that sums to a − t. Thus, in this case, the Partition instance we create consists of the integers S = {v1,…,vn,a−2(a−t)}. Note that a−2(a−t) is non-negative since t > a/2. The rest of the argument is similar to the above.
Therefore, we have shown a Karp reduction from Subset-Sum to Partition such that a Subset-Sum instance is a “yes instance” iff its corresponding Partition instance is also a “yes instance”. Moreover, the reduction can be done in polynomial time since we just need to check if t > a/2 and then we copy the integers V and add a new integer (that is also polynomial-size) to form the Partition instance S.
2. The problem is in NP: the certificate consists of a subset of items whose value is at least the query value q and whose weight is at most the weight limit W . Checking that these conditions hold can be done in polynomial time.
Now we prove NP-hardness by a reduction from the Partition problem which we have shown to be NP-hard previously. Consider a Partition instance with integers v1, . . . , vn. Create a Knapsack Decision instance with n items, where the i-th item has value vi and weight vi. The weight limit of the instance is W = i vi/2 and the query value is q = i vi/2.
There exists a subset of items with total weight at most W and total value at least q 2
if and only if there exists a subset S1 of v1,…,vn such that the sum of S1 is exactly i vi/2. Therefore, we have shown a Karp reduction from Subset-Sum to Partition such that a Partition instance is a “yes instance” iff its corresponding Knapsack Deci- sion instance is also a “yes instance”. The reduction can be done in polynomial time since we just need to create n items with value and weight equal to vi and the weight limit is also polynomial in the sizes of the integers vi.
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.
Solution: (Sketch.) The problem is in NP: The certificate would be the subset S. The certification algorithm does the following: check that S has size k, that S is a subset of L, and that every vertex in R has a neighbor in S. All of this can be done in polynomial time. To prove NP-hardness, we use a reduction from Set Cover. Consider a Set Cover instance with a set U of elements and a collection of subsets S1,…,Sn ⊆ U of elements, and an integer q. Create a Bipartite Covering instance with L representing the subsets S1, . . . , Sn and R representing the set U. In particular, for each subset Si, we have a vertex ui ∈ L; foreachelemente∈U,wehaveavertexve ∈R. Weaddanedgebetweenui andve ifSi contains e. Set the integer k to equal q.
Suppose there exists a set cover of size at most q and let L′ be the vertices of L corresponding to the subsets in the set cover. Then, every vertex in R has a neighbor in L′. Now, suppose that every vertex in R has a neighbor in some subset L′ of L. Then, the corresponding subsets contain every element. Therefore, we have shown a reduction from Set Cover to Bipartite Covering such that a Set Cover instance is a “yes instance” iff its corresponding Bipartite Covering instance is also a “yes instance”. Moreover, the reduction can be done in polynomial time since the number of vertices created is exactly |U|+n and the total number of edges is |U|n.
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) is NP-complete. Using this fact, prove that Degree ∆ Spanning Tree is NP-complete for all fixed ∆ > 2 (D∆ST).
Solution: The problem is clearly in NP: The certificate would be the tree itself. It is trivial to check in polynomial time that the maximum degree is at most ∆ and that it spans all the vertices.
Given an instance G = (V, E) of D2ST we create an instance G′ = (V ′, E′) of D∆ST. Keep the vertices and edges of G; add, for every u ∈ V, ∆−2 dummy nodes du1,…du∆−2 and connect them to u. In other words,
V′ =V ∪{dui |u∈V and1≤i≤∆−2},and E′ =E∪{(u,dui)|u∈V and1≤i≤∆−2}.
Given a D2ST of G we can attach all the dummy nodes (thus increasing the degree of every vertex in V by ∆ − 2) to get a spanning tree of G′ having degree ∆. The other way around also holds, we can trim the dummy nodes (thus reducing the degree of every vertex in V by ∆ − 2) to get a spanning tree of G having degree 2. Therefore, G is a “yes instance” of D2ST if and only if G′ is a “yes instance” of D∆ST. Thus D2ST≤P D∆ST.
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.
3
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.
Solution: While Yes instances of 3-SAT will all be mapped to Yes instances of the Steiner Tree problem, a No instance of 3-SAT may be mapped to a Yes instance of the Steiner Tree problem because there is nothing stopping us from picking both vjT and vjF in S. For example, the formula φ = (¬x1 ∨ ¬x1 ∨ ¬x1) ∧ (x1 ∨ x1 ∨ x1) ∧ (x1 ∨ ¬x1 ∨ x2) is infeasible but it maps to an instance where {v1T , v1F } connect the terminals.
Solution: The problem is clearly in NP. The certificate is the set S of k nodes whose addition to X connects the set, which is trivial to check in polynomial time.
To show that it is NP-hard, we reduce 3-SAT to it. Recall that an instance of 3-SAT consists of a formula φ = C1 ∧ ··· ∧ Cm over variables x1,…,xn such that each clause Ci is the disjunction of three literals. The question is whether there is a truth assignment that satisfies all clauses.
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 a vertex vj ∈ X; we also create a dummy vertex d ∈ X. Additionally, for each variable xj we create two vertices vjT and vjF that belong to V \ X.
2. For each variable xj , we create the edges (vjT , vj ) and (vjF , vj ) to E. For each clause Ci, if Ci contains the literal xj then we create the edge (ui,vjT), while if Ci contains the literal x ̄j then we create the edge (ui,vjF). Finally, we connect d with every vjT and vjF .
3. Finally, we set the target k to be n.
Notice that in order to connect vj with the rest of X we must select either vjT or vjF into the set S; since k = n, exactly one of the them must be chosen for each j = 1,…,n. There is a one-to-one correspondence between truth assignments for the variables and a choice between vjT and vjF for each j = 1,…,n, which will define our set S. It is not difficult to show that a truth assignment is satisfying if and only if for the corresponding S, the graph G[X ∪ S] is connected. (Notice that if we hadn’t added the dummy node d the reduction would not work, why?)
Problem 6
4
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.
Solution: This problem has an easy and correct solution, and a complicated and incorrect solution. The correct solution is to point out that Feedback Set is clearly in NP and that because Set Cover is NP-complete all problems in NP reduce to it, in particular Feedback Set.
The incorrect solution attempts to directly map instances of Feedback Set to Set Cover in the “obvious” way: For each simple cycle in G, we create an element to be covered; for each vertex u in G, we create a set containing all simple cycles going through u. Clearly, every feedback set X induces a set cover of the same cardinality and vice-versa. However, this reduction does not run in polynomial time since there could be an exponential (or worse) number of cycles in the graph!
Problem 7
Prove that Clique is NP-complete by using a reduction from 3-SAT.
Solution: Clique is clearly in NP. Why?
We will reduce 3-SAT to Clique. Specifically, given a 3-CNF formula F of m clauses over n variables, we construct a graph as follows. First, for each clause c of F we create one node for every partial assignment to variables in c that satisfies c. E.g., say we have:
F = (x ∨ x ∨ x ) ∧ (x ̄ ∨ x ∨ x )… 124134
Then in this case we would create nodes like this:
(x1 =0,x2 =0,x4 =1) (x1 =0,x3 =0,x4 =0)…
(x1 =0,x2 =1,x4 =0) (x1 =0,x2 =1,x4 =1) (x1 =1,x2 =0,x4 =0) (x1 =1,x2 =0,x4 =1) (x1 =1,x2 =1,x4 =0) (x1 =1,x2 =1,x4 =1)
(x1 =0,x3 =0,x4 =1) (x1 =0,x3 =1,x4 =0) (x1 =0,x3 =1,x4 =1) (x1 =1,x3 =0,x4 =1) (x1 =1,x3 =1,x4 =0) (x1 =1,x3 =1,x4 =1)
We then put an edge between two nodes if the partial assignments are consistent. Notice that the maximum possible clique size is m because there are no edges between any two nodes that correspond to the same clause c. Moreover, if the 3-SAT problem does have a satisfying assignment, then in fact there is an m-clique (just pick some satisfying assignment and take the m nodes consistent with that assignment). So, to prove that this reduction (with k = m) is correct we need to show that if there isn’t a satisfying assignment to F then the maximum clique in the graph has size < m. We can argue this by looking at the contrapositive. Specifically, if the graph has an m-clique, then this clique must contain one node per clause c. So, just read off the assignment given in the nodes of the clique: this by construction will satisfy all the clauses. So, we have shown this graph has a clique of size m if and only if F was satisfiable.
Also, our reduction is polynomial time since the graph produced has total size at most quadratic in the size of the formula F (O(m) nodes, O(m2) edges). Therefore Clique is NP-complete.
5
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.
Solution: (Sketch.)
1. Edges of a matching do not share any vertex and a vertex cover has to contain at least
one endpoint of each edge so C ≥ M.
2. Let L and R denote the two sides of G. If M = n, then choose all vertices of L or R to be in the vertex cover. Otherwise, the Marriage Theorem implies that there exists a subset S ⊆ L such that |S| > |N(S)|. In this case, the maximum matching is of size n−|S|+|N(S)| and (L\S)∪N(S) is a vertex cover.
3. We have already shown equivalence between all of these problems in class. The above shows equivalence between the Vertex Cover and the Maximum Matching problem. Since there exists a polynomial-time algorithm for the latter, there exists a polynomial- time algorithm for the other problems.
4. A complete graph on 3 vertices, aka a triangle.
6