CSE 421 Assignment #7
Spring 2016

Due: Friday, May 27, 2016.

Reading Assignment: Kleinberg and Tardos Chapter 8

Problems: For all problems on this homework that involve proving NP-completeness, give a full argument that shows that your reduction is correct and runs efficiently and make sure to prove that your problem is in NP also. If you are giving an algorithm, prove that your algorithm is correct and show that it runs efficiently.

1. We wish to design an algorithm to figure out the cost of monitoring the nodes in a computer network represented by a graph G=(V,E). A monitor that is placed at a node in the network can a monitor that node and all of the immediate neighbors of the node. For each node u in the network there is an integer cost c_u of placing a monitor at that node. The Network Monitoring Problem (NMP) is the problem of determining, given the graph G, the costs c_v for each node v in V, and an integer K, whether or not there is a way to place monitors of total cost at most K so that every node in the network is monitored. Prove that the Network Monitoring Problem is NP-complete.

2. Kleinberg and Tardos, Chapter 8, Problem 5, pages 506-507.

3. Suppose that you have a set S of possible labels and are given a directed graph G=(V,E) with a designated start node s with each edge (u,v) having a label L(u,v) which is an element of S. (Note that multiple edges out of a node may have the same label.) In addition, each edge has a probablity p(u,v)≥ 0 of being taken when at u. (That is, for every u in V the sum over all v with (u,v) in E of p(u,v) is 1.) The probability of taking a path begining at the start node s is the product of the probabilities labeling its edges. Use dynamic programming to produce an efficient algorithm that will take as input the directed graph G with its edge labels and edge probabilities and a sequence of labels a₁ ...,a_t and will determine the most likely path beginning at node s that is consistent with the sequence of labels (and determine the probability of that path). You can assume that arithmetic operations on real numbers have cost 1.

4. Extra credit: In this problem you are given a sequence A =a₁,...,a_n of n items from an ordered set U, the numbers f₁,...,f_n where f_i represents the probability that item a_i is requested, and the numbers g₁,...,g_n+1 where g_i represents the probability that there exists a request to some item b in U with a_i-1< b< a_i is requested where we define a₀ to be smaller than every item in U and a_n+1 to be larger than every item in U. (That is, g_i is the total probability that there is a request in the open interval (a_i-1,a_i).) Your goal is to design a binary search tree for A that minimizes the total expected cost of answering a request in the tree, where the cost of answering a request is measured by the number of probes into the search tree that are required to determine whether or a not that requested item is in the tree.