CSPP 55005 Algorithms — Winter 2011
Homework 10 (assigned March 9, due March 16)
Reading: CLRS chapter 35.
Written assignment : Solve the following "Do" exercises and
assigned problems. Only solutions to the assigned problems should be
"Do" Exercises (not to be handed in):
Problems (to be handed in):
CLRS Exercise 35.2-3, page 1117.
2nd edition, page 1033.
CLRS Exercise 35.2-4, page 1117.
2nd edition, page 1033.
CLRS Exercise 35.3-3, page 1122.
2nd edition, page 1038.
CLRS Problem 35-3, page 1135.
2nd edition, page 1050.
Consider the following heuristic for vertex cover. Construct a DFS tree of the
graph G = (V, E), and delete all the leaves from this tree. What
remains must be a vertex cover of the graph. Prove that the size of this cover is at most
twice as large as optimal. (5 points)
The maximum cut problem for an undirected graph G = (V, E) seeks to
partition the vertices V into disjoint sets A and B so as to maximize
the number of edges (a, b) ∈ E such that a ∈ A
and b ∈ B. Give a deterministic polynomial-time approximation algorithm
for this problem with a ratio bound of 2. Describe your algorithm in pseudocode. (8 points)
Analyze its running time. (2 points) Prove that its ratio bound is 2. (5 points)
Hint: Your algorithm should guarantee that the number of edges crossing the cut is at least
half the total number of edges.
CLRS Problem 35-4, parts a–f, page 1135. Write pseudocode for part b.
(8 points for part b; 5 points each for the remaining parts)
2nd edition, page 1051.
Optional problem (7 points): A communications network, modeled by a directed graph
G = (V, E), has c user requests. User i, for each
i = 1, 2, … c, issues a request to reserve a specific path
Pi in G on which to transmit data. The network is
interested in accepting as many of these path requests as possible, subject to the
following restriction: if both Pi and Pj
are accepted, then Pi and Pj cannot
share any nodes.
Problem statement: Given a directed graph G = (V, E),
a set of requests P1, …, Pc, each of
which must be a path in G, and a number k, is it possible to select at
least k of the paths so that no two of the selected paths share any nodes?
Prove that this problem is NP-Complete.
See DPV Exercise 8.23, page 266,
(online page 282), for hints. Note that you need not reduce from 3-SAT.
Gerry Brady and Janos Simon
Wednesday March 9 23:29:59 CST 2011