Sample problems for tutorial #5

1. In this question we consider two problems:
   • The Emergency Distribution Problem (EDP) consists of a an undirected, unweighted graph G = (V, E) plus a set of distribution points D = { d₁, d₂, .., d_k }, each a vertex in V and a single aid location a ∈ V that is not in D. The output is the number of non-overlapping (edge-wise distinct) paths leading from some d_i to a. (Multiple paths may lead from a single distribution point, and paths may lead from different distribution points.)
   • You have an efficient algorithm to solve the "network bandwidth problem" (NBP). NBP's input is a weighted, directed graph G = (V, E), where the tuple (u, v, w) ∈ E represents a directed edge from u to v with integer weight w and designated source and target vertices s and t. A node in the graph is a server and an edge is a network link between servers, weighted by its bandwidth---the maximum number of bytes per second the link can carry. (A weight of ∞ is also allowed, indicating unlimited bandwidth.)

     NBP's output is the maximum bandwidth that can be carried from s to t.

     Notes: The bandwidth on any link cannot exceed that link's weight. The bandwidth coming out of s is unlimited but none can go in, while unlimited bandwidth can go into t but none can come out. Otherwise, for any node v, the bandwidth coming into the node must equal the bandwidth coming out. Assume only integral (or infinite for links with weight ∞) amounts of bandwidth can be used on each edge.

   Consider the following incorrect reduction from EDP to NBP:

   • For each node v ∈ V_EDP, generate a corresponding node v in V_NBP.
   • For each undirected edge (u, v) ∈ E_EDP, generate two edges (u, v, 1) and (v, u, 1) in E_NBP.
   • Generate one additional vertex v' in V_NBP.
   • For each distribution point d ∈ D, generate an edge (v', d, 1) ∈ E_NBP.
   • Finally, let s = v' and t = a.

   Answer the following questions:

   1. Give a good counterexample to the correctness of this reduction. (A drawing of the counterexample instance is an excellent way to express it.)
   2. Give the instance of NBP produced by the reduction from your counterexample. (Again, a drawing works well.)
   3. Give and very briefly explain the incorrect solution to the original instance produced by the reduction (paired with an arbitrary solution to the underlying problem).
   4. Give and very briefly explain the correct solution to the original instance.
2. In the Exhibition Guarding Problem, we are given a line L that represents a long hallway in a show room. We are also given an unordered set X = { x₀, x₁, ... x_n-1 } of real numbers that represent the positions of precious objects or sculptures in this hallway. Suppose that a single guard can protect all the objects within distance at most d of his or her position, on both sides.

   • Design an algorithm for finding a placements of guards that uses the minium number of guards to guard all the objects with positions in X.
   • Analyze the running time of your algorithm as a function of n, the number of objects that need guarding.
   • Sketch a proof that your algorithm works.