Description
1. (15 pts total) A matching in a graph G is a subset EM ⊆ E(G) of edges such that
each vertex touches at most one of the edges in EM. Recall that a bipartite graph is a
graph G on two sets of vertices, V1 and V2, such that every edge has one endpoint in
V1 and one endpoint in V2. We sometimes write G = (V1, V2; E) for this situation. For
example:
V1 : 1 2 3 4 5 6
V2 : 7 8 9 10 11
The edges in the above example consist of all the lines, whether solid or dotted; the
solid lines form a matching.
The bipartite maximum matching problem is to find a matching in a given bipartite
graph G , which has the maximum number of edges among all matchings in G.
(a) Prove that a maximum matching in a bipartite graph G = (V1, V2; E) has size at
most min{|V1|, |V2|}.
(b) Show how you can use an algorithm for max-flow to solve bipartite maximum
matching on undirected simple bipartite graphs. That is, give an algorithm
which, given an undirected simple bipartite graph G = (V1, V2; E), (1) constructs a directed, weighted graph G0
(which need not be bipartite) with weights
w : E(G0
) → R as well as two vertices s, t ∈ V (G0
), (2) solves max-flow for
(G0
, w), s, t, and (3) uses the solution for max-flow to find the maximum matching in G. Your algorithm may use any max-flow algorithm as a subroutine.
(c) Show the weighted graph constructed by your algorithm on the example bipartite
graph above.
2. (20 pts total) In the review session for his Deep Wizarding class, Dumbledore reminds
everyone that the logical definition of NP requires that the number of bits in the witness
w is polynomial in the number of bits of the input n. That is, |w| = poly(n). With
a smile, he says that in beginner wizarding, witnesses are usually only logarithmic in
size, i.e., |w| = O(log n).
(a) Because you are a model student, Dumbledore asks you to prove, in front of the
whole class, that any such property is in the complexity class P.
(b) Well done, Dumbledore says. Now, explain why the logical definition of NP implies
that any problem in NP can be solved by an exponential-time algorithm.
1
CSCI 3104
Problem Set 10
(c) Dumbledore then asks the class: “So, is NP a good formalization of the notion of
problems that can be solved by brute force? Discuss.” Give arguments for both
possible answers.
3. (30 pts total) The Order of the Phoenix is trying to arrange to watch all the corridors
in Hogwarts, to look out for any Death Eaters. Professor McGonnagall has developed
a new spell, Multi-Directional Sight, which allows a person to get a 360-degree view
of where they are currently standing. Thus, if they are able to place a member of
the Order at every intersection of hallways, they’ll be able to monitor all hallways.
In order not to spare any personnel, they want to place as few people as possible at
intersections, while still being able to monitor every hallway. (And they really need
to monitor every hallway, since Death Eaters could use Apparition to teleport into
an arbitrary hallway in the middle of the school.) Call a subset S of intersections
“safe,” if, by placing a member of the Order at each intersection in S, every hallway
is watched.
(a) Formulate the above as an optimization problem on a graph. Argue that your
formulation is an accurate reflection of the problem. In your formulation, show
that the following problem is in NP: Given a graph G and an integer k, decide
whether there a safe subset of size ≤ k.
(b) Consider the following greedy algorithm to find a safe subset
S = empty
mark all hallways unwatched
while there is an unwatched intersection
pick any unwatched hallway; let u,v be its endpoints
add u to S
for all hallways h with u as one of its endpoints
mark h watched
end
end
Although this algorithm need not find the minimum number of people needed
to cover all hallways, prove that it always outputs a safe set, and prove that it
always runs in polynomial time.
(c) Note that, in order to be polynomial-time, an algorithm for this problem cannot
simply try all possible subsets of intersections. Prove why not.
(d) Give an example where the algorithm from (3b) outputs a safe set that is strictly
larger than the smallest one. In other words, give a graph G, give a list of vertices
2
CSCI 3104
Problem Set 10
in the order in which they are picked by the algorithm, and a safe set in G which
is strictly smaller than the safe set output by the algorithm.
(e) Consider the following algorithm:
S = empty
mark all hallways unwatched
while there is an unwatched hallway
pick any unwatched hallway; let u,v be its endpoints
add u,v to S
for all hallways h with u or v one of their endpoints
mark h watched
end
end
Prove that this algorithm always returns a safe set, and runs in polynomial time.
(f) In any safe set of intersections, each hallway is watched by at least one member
of the Order. Use this to show that the algorithm from (3e) always outputs a safe
set whose size is no more than twice the size of the smallest safe set. Note: you
don’t need to know what the smallest safe set is to prove this! All you need is the
fact stated here.
This is called a “2-approximation algorithm,” because it is guaranteed to output
a solution that is no worse than a factor of 2 times an optimal solution.
(g) Does the algorithm from (3b) always produce a safe set no bigger than that produced by the algorithm in (3e)? If so, give a proof; if not, give a counterexample.
A counterexample here consists of a graph, and for each algorithm, the list of
vertices it chooses in the order it chooses them, such that the safe set output by
algorithm (3b) is at least as large as the safe set output by algorithm (3e). If you
are unable to give either a proof or a counterexample, then for partial credit give
a plausible intuitive argument for your answer.
(h) Compare the greedy algorithm from (3e) with the greedy algorithm from (3b).
Show which runs faster asymptotically? Which of these two algorithms would
you rather use to solve the Order of the Phoenix’s problem and why?
(i) This problem is, in fact, NP-complete. Why does the 2-approximation polynomialtime algorithm from (3e) not show that P=NP?1
1
Interestingly, it is known that if there were a 1.3606…-approximation algorithm for this problem in
polynomial time, then it would follow that P=NP, but that is a very nontrivial theorem. Under a standard
complexity-theoretic assumption, even if there were a 1.99999-approximation algorithm in polynomial time,
3
CSCI 3104
Problem Set 10
4. (20 pts extra credit) Every young wizard learns the classic NP-complete problem of
determining whether some unweighted, undirected graph G = (V, E) contains a simple
path of length at least k (where both G and k are part of the input to the problem),
known as the Longest Path Problem. Recall that a simple path is a path (v1, v2, . . . , v`)
where each (vi
, vi+1) in the path is an edge, and all the vi are distinct; its length is
` − 1 (=the number of edges in the path).
(a) Ginny Weasley is working on a particularly tricky instance of this problem for
her Witchcraft and Algorithms class, and she believes she has written down a
“witness” for a particular input (G, k) in the form of a path P on its vertices.
Explain how she should verify in polynomial time whether P is or is not simple
path of length ≥ k. (And hence, demonstrate that the problem of Longest Path
is in the complexity class NP.)
(b) For the final exam in Ginny’s class, each student must visit the Oracle’s Well in
the Forbidden Forest. For every bronze Knut a young wizard tosses into the Well,
the Oracle will give a yes or no response as to whether, given an arbitrary graph
G and an integer k, G contains a simple path of length ≥ k. Ginny is given an
arbitrary graph G and must find the longest simple path in G.
First, she realizes it would be useful to determine the length of the longest simple
path. Describe an algorithm that will allow Ginny to use the Oracle to find the
length of the longest simple path in G by asking it a series of questions, each involving a modified version of the original graph G and a number k. Her solution
must not cost more Knuts than a number that grows polynomially as a function
of the number of vertices in G. (Hence, prove that if we can solve the Longest
Path decision problem in polynomial time, we can solve its optimization problem
as well.)
(c) Next, once she knows the length ` of the longest simple path in G, Ginny muse
use the Oracle to actually find a path of length `. Describe an algorithm that will
allow Ginny to use the Oracle to find the longest simple path in G by asking it a
series of questions, each involving a modified version of the original graph G and a
number k of her choosing (for each question she can ask about a different graph G
and a different number k). Her solution must not cost more Knuts than a number
that grows polynomially as a function of the number of vertices in G. (Hence,
it would follow that P=NP, but this assumption remains a conjecture, and opinion in the research community
is divided on whether this conjecture is true or false. We will provide references to these results after the
problem set has been handed in.
4
CSCI 3104
Problem Set 10
prove that if we can solve the Longest Path decision problem in polynomial time,
we can solve its search problem as well.)
5. (20 pts extra credit) Recall that the MergeSort algorithm (Chapter 2.3 of CLRS) is
a sorting algorithm that takes Θ(n log n) time and Θ(n) space. In this problem, you
will implement and instrument MergeSort, then perform a numerical experiment that
verifies this asymptotic analysis. There are two functions and one experiment to do
this.
(i) MergeSort(A,n) takes as input an unordered array A, of length n, and returns
both an in-place sorted version of A and a count t of the number of atomic operations
performed by MergeSort.
(ii) randomArray(n) takes as input an integer n and returns an array A such that for
each 0 ≤ i < n, A[i] is a uniformly random integer between 1 and n. (It is okay if A is
a random permutation of the first n positive integers; see the end of Chapter 5.3.)
(a) From scratch, implement the functions MergeSort and randomArray. You may
not use any library functions that make their implementation trivial. You may use
a library function that implements a pseudorandom number generator in order to
implement randomArray.
Submit a paragraph that explains how you instrumented MergeSort, i.e., explain
which operations you counted and why these are the correct ones to count.
(b) For each of n = {2
4
, 2
5
, . . . , 2
26
, 2
27}, run MergeSort(randomArray(n),n) fives
times and record the tuple (n,hti), where hti is the average number of operations
your function counted over the five repetitions. Use whatever software you like to
make a line plot of these 24 data points; overlay on your data a function of the
form T(n) = A n log n, where you choose the constant A so that the function is
close to your data.
Hint 1: To increase the aesthetics, use a log-log plot.
Hint 2: Make sure that your MergeSort implementation uses only two arrays of
length n to do its work. (For instance, don’t do recursion with pass-by-value.)
5
