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|).