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 turned in.

"Do" Exercises (not to be handed in):

1. CLRS Exercise 35.2-3, page 1117.
   2nd edition, page 1033.

2. CLRS Exercise 35.2-4, page 1117.
   2nd edition, page 1033.

3. CLRS Exercise 35.3-3, page 1122.
   2nd edition, page 1038.

4. CLRS Problem 35-3, page 1135.
   2nd edition, page 1050.

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

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

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

4. 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 P_i 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 P_i and P_j are accepted, then P_i and P_j cannot share any nodes.
   Problem statement: Given a directed graph G = (V, E), a set of requests P₁, …, P_c, 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.