CMPUT 304: Algorithms II Fall 2021
Assignment 5 (Due Dec 9 by 11:55pm): Submit via eClass
You must adhere to the consultation collaboration policy mentioned in the course outline. Remember to list
anyone you discussed the assignment questions with and remember what constitutes an acceptable level of
discussion.
You need to solve 5 out of the 6 problems. Each is worth 8 marks, so the total score is 40. If you solve all 6,
the TAs get to decide which ones they want to mark.
Your solutions must be written neatly. Messy solutions that are difficult to read may lose marks or may
even receive a 0 if it takes the TA too much effort to even understand what you have written. If you are not
typesetting your solution in LaTeX or even something like Word (remember to export as a .pdf), then take your
time writing things neatly!
Short and to-the-point answers are best. Rambling answers may not receive full credit.
Problem 1 – Constructing Solutions if P = NP [8 marks]
Recall that in the Vertex Cover problem, you are given a graph G = (V,E) and an integer k. The goal is to
determine if there is some C ⊆ V with |C| ≤ k such that each {u, v} ∈ E has at least one of u or v in C.
If P = NP, then this decision problem can be solved in polynomial time. But merely knowing the answer is
“yes” for an instance does not give you the actual vertex cover!
Show that if P = NP then there is an algorithm that does the following. Given a yes instance G, k of Vertex
Cover, the algorithm computes a feasible solution in polynomial time: that is it finds a vertex cover C ⊆ V
with |C| ≤ k in polynomial time. Argue why your algorithm is correct (assuming P = NP) and explain why it
runs in polynomial time.
Problem 2 – co-NP-completeness [8 marks]
We say a language L ⊆ {0, 1}∗ is co-NP-complete if L ∈ co-NP and ∀L′ ∈ co-NP, L′ ≤P L.
Let 3DNF-Tautology be the following problem. Read the description carefully!
We are given n variables x1, . . . , xn and m clauses. Each clause is of the form `1∧`2∧`3 where each `i is a literal
(a variable or its negation) and these three literals depend on different variables. We say a clause is satisfied
by a truth assignment if all of its literals are true under this assignment. The goal of 3DNF-Tautology is
to determine if all variable assignments will satisfy at least one clause (a yes instance) or if there exists an
assignment that fails to satisfy every clause (a no instance).
Show that 3DNF-Tautology is co-NP-complete.
Strong Hint: Use the fact that L ∈ NP if and only if L ∈ co-NP. So starting from any L′ ∈ co-NP,
consider using reductions we already know from NP-completeness in L′. Show how 3CNF-SAT and 3DNF-
Tautology are related (tip: DeMorgan’s rule).
5-1
5-2 Assignment 5: Submit via eClass
Problem 3 – Two Quick Approximation Algorithms [8 marks]
Part 1 [4 marks]
Let G = (V,E) be a graph. Give an algorithm that finds a colouring σ : V → {1, 2, 3} of the nodes such that
the number of edges {u, v} ∈ E with σ(u) 6= σ(v) is at least 2
3
· |E|. Your algorithm is allowed to be randomized,
so long as the expected number of edges whose endpoints are coloured differently is at least 2
3
· |E|.
Part 2 [4 marks]
In an instance of NAE-3SAT, we are given an instance of 3CNF-SAT except a clause is said to be satisfied by
a truth assignment if there is at least one true literal and at least one false literal in the clause. For example,
consider a clause x∨ y ∨ z. The assignment x = T, y = T, z = T is satisfying since there are both true and false
literals. However, the assignment x = T, y = Y, z = F is not satisfying since there are no false literals. Recall
this problem was discussed during the seminar on Nov 17.
Give an algorithm that satisfies at least 3m/4 clauses where m is the total number of clauses. Again, the
algorithm is allowed to be randomized so long as the expected number of clauses that are satisfied is at least
3m/4.
Bonus [1 mark]
Give a deterministic (i.e. not randomized), polynomial time that is guaranteed to find a truth assignment
satisfying at least 3m/4 clauses of a NAE-3SAT instance.
Problem 4 – TSP Path [8 marks]
Let T = (V,E) be a tree and s, t ∈ V be two distinct vertices. Show that there is an s − t walk in the tree (a
path, but repeating vertices is allowed) such that each vertex in V is visited at least once by the walk and each
edge in E is traversed by this walk at most twice.
Use this to give a 2-approximation for the following problem: given a points V with metric distances d(u, v)
between points u, v ∈ V (recall the metric properties from the lecture 18) and two distinct nodes s, t, find a
cheapest TSP Path solution. Here, a TSP path solution is an ordering v1, v2, . . . , vn of V (so n = |V |) with
v1 = s and vn = t. That is, the ordering describes an s− t path that visits all points. The cost of the ordering
is:
n−1∑
i=1
d(vi, vi+1).
Note, the cost does not include the cost of the step from vn to v1. Informally, find the cheapest path from s
to t that visits all points.
Hint: Adapt the steps from the 2-approximation for metric TSP from the lectures. Use the fact about trees
from the first part to help out.
Problem 5 – Maximum (Non-Bipartite) Matching [8 marks]
Problem 35-4 in the textbook, parts (b) through (f) (you can think about part (a) if you want, but you do not
need to submit it).
Ultimately, you just have to give an O(|E|) algorithm for computing a matching M with size at least half that
of a maximum matching. If you choose to do this differently than following parts (b) through (f), go ahead.
Assignment 5: Submit via eClass 5-3
Notation: Part (d) talks about a subgraph induced by a set of nodes. This means the following: let G = (V,E)
be a graph. For a set S ⊆ V , the subgraph of G induced by S is the graph:
(S, F ) where F = {{u, v} ∈ E : u, v ∈ S}.
That is, the subgraph of G obtained by deleting all nodes in V − S and edges that touch at least one of the
deleted nodes, but keeping all edges having both endpoints in S.
Note: One can actually find a maximum matching in any graph in polynomial time, but it takes a lot more
effort than the case with bipartite graphs (i.e. it does not just reduce to flow).
Problem 6 – Parallel Machine Scheduling [8 marks]
Problem 35-5 in the textbook. For part (c), don’t worry about finding a solution with optimal running time.
Just make sure your algorithm runs in polynomial time. But it is a good exercise to think about how fast you
could implement it.