## Description

1. [20 points] My lecture slides (and KT section 8.2) show a reduction from SAT to Independent Set. Apply it to

the Boolean formula:

(x1 ∨ x2 ∨ x4) ∧ (x1 ∨ ¬x2 ∨ x3) ∧ (x2 ∨ ¬x3 ∨ ¬x4)

(a) Show the resulting graph and integer “k.” Although the graph is technically just an ordinary undirected

graph, with no vertex- or edge labels of any kind, in the reduction there is a natural correspondence between

literals/clauses in the formula and vertices/vertex groups in the graph; show this somehow on your graph

drawing. (Please try to draw your graph neatly and clearly; e.g., it’s a planar graph—can be drawn in 2D

without any edges crossing each other). It’s hard to grade a hairball!)

(b) The formula has many satisfying assignments, and the resulting graph has many independent sets. The correctness proof for the reduction defines a correspondence between the two. In particular, given a satisfying

assignment, the proof explains how to choose one (or more) independent sets. For your graph, what set

corresponds to the assignment x1 = x2 = x3 = F alse, x4 = T rue? (There should only be one.) Given

that independent set, what assignments correspond to it? (There should be two.) Are they both satisfying

assignments?

2. [20 points] In lecture I showed a reduction from SAT to Subset Sum (SS; aka KNAP). Apply it to the Boolean

formula:

(x1 ∨ x2 ∨ x4) ∧ (x1 ∨ ¬x2 ∨ x3) ∧ (x2 ∨ ¬x3 ∨ ¬x4)

(a) Show us the resulting SS instance. Although the SS instance is technically just a list of numbers, with

no labels of any kind, in the reduction there is a natural correspondence between literals/clauses in the

formula and numbers or parts of numbers in the SS instance; show this somehow.

(b) The formula has many satisfying assignments, and the SS instance has many subsets summing to the

specified target C. The correctness proof for the reduction defines a correspondence between the two. In

particular, given a satisfying assignment, it explains how to choose one (or more) SS subsets whose total is

C. For your SS instance, what subsets correspond to the assignment x2 = x3 = F alse, x1 = x4 = T rue?

(There should four.) Given any of those subsets, what assignment(s) correspond to it? Are they satisfying

assignments?

3. [20 points] The MaxCut problem is the following: given an undirected graph G = (V, E) and an integer k, is

there a partition of the vertices into two (nonempty, nonoverlapping) subsets V1 and V2 so that k or more edges

have one end in V1 and the other end in V2?

(a) Prove that MaxCut is in NP. Carefully, separately, describe the components that are central to the definition

of membership in NP (slide ≈60; KT §8.3):

i. What, precisely, is the “hint” / “certificate” / “witness” you envision for this problem?

ii. How long is it?

iii. What does the “verifier” do with it? In particular,

• How does the verifier conclude that a specific “hint” proves that this is a “yes” instance of MaxCut,

vs

• What would cause the verifier to conclude that a specific “hint” fails to prove this? Why can’t any

“hint” for a “no” instance “fool” the verifier into saying “yes” when it shouldn’t?

1

iv. Asymptotically, as a function if the length of the MaxCut instance and the length of the “hint”, how

much time does it take to run the verifier?

(b) Give an algorithm for MaxCut and analyze its running time. (A non-polynomial-time algorithm shouldn’t

be a big surprise.)

I want moderately detailed proofs/algorithms here, as in my slides concerning the definition of NP (numbered

≈48-74; see also KT §8.3).

Note: Recall that P is a subset of NP. The same facts can be established in almost the same way for the analogous

MinCut problem (defined like MaxCut, except ≤ k instead of ≥ k). In fact, MinCut is in P (using Max Flow/Min

Cut tools; see KT chapter 7 and section 13.2, if you’re interested), whereas MaxCut is known to be NP-complete

(but you don’t need to prove it). So, showing that a problem is in NP doesn’t necessarily mean that all algorithms

for it will be slow, although that becomes increasingly likely if you can’t find a polynomial time algorithm after

concerted effort, or, even better, if you prove it to be NP-complete.

4. [20 points] For any fixed integer k ≥ 2, the k-PARTITION PROBLEM (abbreviated ‘k-PP’) is: given a sequence

of positive integers (w1, w2, . . . , wn), is it possible to partition them into k groups having equal sums. More

formally, is there an n-vector h each of whose entries is a integer in the range 1, . . . , k such that, for each

1 ≤ j ≤ k:

−1

[j] = {i | h[i] = j}. For example, (1, 2, 1, 3, 1, 1) is a “yes” instance of 3-PP, but a “no” instance of

4-PP; (3, 2, 1, 3, 3) is the reverse.

(a) As in the previous problem, carefully show that k-PP is in NP.

(b) Give an algorithm for k-PP and analyze its running time.

(c) Show that 2-PP ≤p KNAP (slide 36). (Make sure all the pieces required by my definition of reduction—

slide 33—are carefully explained.)

(d) Suppose I could show that there is no polynomial time algorithm for KNAP. Would this together with 4c

imply that there cannot be a polynomial time algorithm for 2-PP? Explain why or why not.

(e) Extra Credit: Show KNAP ≤p k-PP for each k ≥ 2. Hint: start with k = 2.

5. [20 points] Give an algorithm to construct an Euler tour (slide 51) in a connected, undirected graph in which all

degrees are even. (Recall, the “degree” of a vertex in a graph is the number of edges touching it.) Assume the

graph is represented by edge lists. Your algorithm should run in time O(|V | + |E|).