Consider the following problem that arises in the design of broadcasting schemes for netwo...

Consider the following problem that arises in the design of broadcasting schemes for networks. We are given a directed graph G = (V, E), with a designated node r e V and a designated set of "target nodes" T c V -{r}. Each node v has a switching time sv, which is a positive integer.

At time 0, the node r generates a message that it would like everynode in T to receive. To accomplish this, we want to find a scheme whereby r tells some of its neighbors (in sequence), who in turn tell some of their neighbors, and so on, until every node in T has received the message. More formally, a broadcast scheme is defined as follows. Node r may send a copy of the message to one of its neighbors at time 0; this neighbor will receive the message at time 1. In general, at time t > 0, any node v that has already received the message may send a copy of the message to one of its neighbors, provided it has not sent a copy of the message in any of the time steps t - sv + 1, t - sv + 2,t - 1. (This reflects the role of the switching time; v needs a pause of sv – 1 steps between successive sendings of the message. Note that if sv = 1, then no restriction is imposed by this.)

The completion time of the broadcast scheme is the minimum time t by which all nodes in T have received the message. The Broadcast Time Problem is the following: Given the input described above, and a bound b, is there a broadcast scheme with completion time at most b?

Prove that Broadcast Time is NP-complete.

Example. Suppose we have a directed graph G = (V, E), with V = {r, a, b, c}; edges (r, a), (a, b), (r, c); the set T = {b, c}; and switching time sv = 2 for each v e V. Then a broadcast scheme with minimum completion time would be as follows: r sends the message to a at time 0; a sends the message to b at time 1; r sends the message to c at time 2; and the scheme completes at time 3 when c receives the message. (Note that a can send the message as soon as it receives it at time 1, since this is its first sending of the message; but r cannot send the message at time 1 since sr = 2 and it sent the message at time 0.)