Cs 3510 hw10 sol - Dana Randall PDF

Preview

Summary

Dana Randall...

Description

CS 3510-B Homework 10 Solutions You must submit this homework on Gradescope. You can work together on homeworks, but you must write up solutions by yourself. Exams and homework are similar, so it is in your best interest to try to solve problems by yourself. 1. Formulate the following optimization problems as decision problems. Then show that they are in NP by explaining what nondeterministic information could be verified and what the verifier would do. (1a) Given a CNF (SAT) formula, find a truth assignment that satisfies the maximum number of clauses. Solution. The decision version of this problem is: given a CNF formula and integer k, is there a truth assignment that satisfies at least k clauses? Take the truth assignment to be the certificate, which is clearly polynomially-bounded in the size of the input. The verifier takes the CNF formula, k, and the certificate as input and starts by substituting in the truth values of the literals. It then determines if at least k clauses are satisfied in polynomial time.

(1b) A vertex cover is a subset of vertices C ⊆ V so that every vertex in V is either in C or has a neighbor in C. Given a graph, how small is the smallest vertex cover? Solution. The decision version of this problem is: given a graph and integer k, is there a vertex cover of size at most k ? Let the certificate be a subset of vertices S ⊆ V . Clearly the size is polynomially-bounded by the size of the input. The verifier takes the graph G, threshold k and a subset S as input. It first checks that |S| ≤ k, and then it verifies that S is indeed a vertex cover in polynomial time. To do this, it loops over each vertex v in G and checks that v ∈ S or a neighbor of v is in S. An upper bound on the running time is O(|V | · (|V | + |E|)). If this condition is true for all vertices, the verifier outputs YES since S is a vertex cover of size at most k. Otherwise it outputs NO.

1

(1c) Traveling salesman: You are given a set of vertices and a distance matrix telling you the distances between all pairs of vertices. Find the shortest tour that visits each vertex exactly once. Solution. The decision version of this problem is: given a set of vertices, distance matrix telling you the distances between all pair of vertices, and a threshold k, is there a tour through all the vertices of distance at most k ? A certificate for this decision problem is a sequence of vertices that defines the order of the tour. If a tour exists, an upper bound on the number of edges used in the tour is |V | · |E | since we can start at vertex 1, take the shortest path to vertex 2, then take the shortest path from vertex 2 to vertex 3, etc. In each of these shortest path segments, at most |E| edges are used. Therefore, this gives us a bound of O(|V | · |E|) on the size of the certificate, as desired. The verifier takes as input the graph G, distance matrix A, threshold k, and the certificate. To verify the certificate (v1 , v2 , . . . , vℓ , vℓ+1 ) it first checks that each (vi , vi+1) ∈ E is actually an edge. Next it verifies that v1 = vℓ+1 so that we indeed have a tour. Last, it computes the total tour length via the distance matrix as tour distance =

ℓ X

A(i, i + 1),

i=1

and returns true if tour length ≤ k and the tour is valid. Otherwise, it returns false.

2

2. The PRIMALITY problem asks whether an integer is prime or not. Show that PRIMALITY is in P if the input is given in unary rather than binary. Concretely, show that the language L = {1p : p is prime} is in P. Solution. Consider the following algorithm for an input x ∈ {0, 1}n . If x contains a 0 bit, then return false since x 6∈ L. Now we assume that x = 1n . For each integer 2 ≤ d < n, determine if d divides n. This can be done in O(n) time for each d by considering multiples of d. If any d divides n then output false, otherwise output true. The total running time of this algorithm is O(n2 ) which is polynomial in the input length n.

Now consider the PRIMALITY problem when the input is given in binary. Is it obvious that PRIMALITY is in NP? Its complement COMPOSITENESS asks whether an integer n is composite. Both decision problems are in NP because they are in P, but which of the two problems is obviously in the class NP for binary inputs and why? Solution. Let x ∈ {0, 1}n be the binary input for an integer N . Since n = ⌈log2 (N )⌉ it is not obvious that there is a polynomial-bounded size certificate that N is prime as there are N −2 = Θ(2n ) integers in {2, 3, . . . , N − 1}, all of which should not divide N . It is much easier to show that COMPOSITENESS is in N P since for a composite input x ∈ {0, 1}n the certificate of compositeness can just be a divisor d of N . The number of bits needed to encode d is at most that of N since d ≤ N . Moreover, we can efficiently verify that d divides N in O(n2 ) time. Therefore, COMPOSITENESS is clearly in NP for binary inputs.

3

3. STINGY-SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists. Prove that STINGY-SAT is NP-complete. Solution. First we show that STINGY-SAT is in NP. A certificate for a YES instance is simply the truth assignment for the variables, which is polynomially bounded by the size of the input. The verifier should first check that at most k of the variables are set to true, which can be done in polynomial time. If this condition is met, then the verifier should check that the truth assignment actually satisfies the input formula. This can also be done in polynomial time since the formula is in conjunctive normal form. Now we show that STINGY-SAT is NP-hard by reducing 3SAT to STINGY-SAT. Given a 3-SAT instance, we can directly give it to STINGY-SAT as input with k set to be the number of variables in the 3-SAT formula. STINGY-SAT outputs YES if and only if the 3-SAT formula is satisfiable. Therefore, STINGY-SAT is at least as hard as 3-SAT and therefore NP-hard. Since STINGY-SAT is in both NP and NP-hard, it follows that STINGY-SAT is in NPcomplete.

4

4. Consider an undirected graph G with source vertices s1 , s2 , . . . sk and sink vertices t1 , t2 , . . . , tk . The NETWORK-ROUTING decision problem asks whether there are k node disjoint paths where the i-th path goes from si to ti . Show that this problem is NP-complete. Hint: Reduce from 3-SAT. For a 3-SAT formula with q clauses and n variables, use k = q + n sources and sinks. Introduce one source/sink pair (sx , tx ) for each variable x, and one source/sink pair (sc , tc ) for each clause c. Now, for each 3-SAT clause, introduce (at most) 6 new intermediate vertices, one for each literal occurring in that clause and one for the negation of that literal. Now finish this off by noticing that if the path from sc to tc goes through a vertex representing a variable x, then no other path can go through that vertex. What other vertex would you like that path to go through instead? Solution. We start by describing the reduction from 3-SAT to NETWORK-ROUTING. For each of the q clauses c, for example (x1 ∨ ¬x2 ∨ x3 ), independently construct the bipartite gadget below with source sc and sink tc .

The idea here is that any path from sc to tc defines exactly one setting of the variables in the clause. As of now each clause is independent of the others, so there is no requirement that all paths need to satisfy the same global truth assignment to the variables x1 , x2 , . . . , xn . Now we demonstrate how to connect the clauses so that the truth assignment is consistent across all clauses. Since there are n variables in the formula, introduce n additional sources and sinks, say s1 , s2 , . . . , sn and t1 , t2 , . . . , tn . For each variable xi , thread paths from si to ti through all xi and ¬xi nodes in all of the clauses. See the figure below illustrating the construction for the formula (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x1 ∨ ¬x2 ∨ x4 ). We briefly explain the correctness of this reduction. Clearly this graph G can be constructed in time polynomial in the size of the 3-SAT formula. Therefore, the resulting graph is also of polynomial size. If the 3-SAT formula f (x1 , x2 , . . . , xn ) has a satisfying solution, then the constructed graph has a networking routing. To see this, if x1 is true in the truth assignment then route the path from s1 to t1 through all of the x1 variables in the clauses. Because paths must be node disjoint, this has the effect of blocking any clause routing from going through a x1 node. However, if the assignment is satisfying, then there is a routing for each clause source/sink pair through the negatives of the variable assignment. Therefore, there exists a node-disjoint routing in this graph.

5

Solution. Next, if there exists a routing in this graph, then we can similarly argue that there must be a satisfying assignment for the formula f (x1 , x2 , . . . , xn ). Therefore, this instance of NETWORK-ROUTING is true if and only if the 3-SAT instance is satisfiable. Together with the polynomial-sized construction, we have shown that 3-SAT reduces to NETWORKROUTING, as desired.

6...