Minimum number of rounds to notify a hierarchy of people with DP

Question

I'm trying to figure out a problem reported in Kleinberg (ch 6 no.16). I know that there are solutions based on ordering, anyway i'd like to understand if another way exists.

Basically, we have a hierarchy of people represented by a tree. The root person has to postpone a picnic due to rain: in a first moment he calls by phone his direct subordinates, one at a time. As soon as each subordinate gets the phone call, he must notify each of his direct subordinates, one at a time. This continues until everyone has been notified. Any person at a node can notify only his own children in the tree (e.g. no grandchildren).

You can view this process as being devided in rounds: in one round, every person who has been notified can call one of his subordinates (thus in parallel).

It's important to note that the number of rounds required to notify everyone depends on the sequence in which each person calls their direct subordinates. E.g. with the following tree we have 2 rounds if A notifies B first, or 3 rounds if A decides to start from D:

The problem requires an efficient algorithm that determines the minimun number of rounds. My approach is the following: like in largest independent set i obtain first a post order transversal $v_1, v_2, \ldots, v_n$ of the whole tree. Then i define the following recurrence relation:

$$ OPT(v_i)= \begin{cases} 0 \qquad \qquad \qquad \qquad \qquad \qquad \quad \hbox{if leaf} \\ \displaystyle\max_{v_j\ \text{child of}\ v_i}\left\{k(v_i), 1 + OPT(v_j)\right\} \ \hbox{otherwise} \end{cases} $$

Where $k(v_i)$ is the children count of the node $v_i$, and $OPT(v_i)$ is the minimum number of rounds required to notify the people contained in the subtree with $v_i$ as root.

Let's consider a more complex tree:

Due to the recurrence we have $OPT(v_i)_{v_i \in \left\{C, E, F, G, H, I, L \right\}} = 0$, $OPT(B)=4$, $OPT(D)=2$ and finally $OPT(A)=5$ that, as you can see, is exactly the minimum number of rounds to reach every node in the tree.

Please, if my approach is wrong can you give me some hint or counter example showing that ordering is required?

Answer 1

I do not think it is correct.Please consider this example: Suppose $a$ has $k$ children. Two of them($b,c$) are chains of $k+1$ nodes the other are leaves. We have:

1. $OPT(b) = OPT(c) = k$
2. All other $OPT$ are zeroes.

According to your algorithm we should have $OPT(a)=1+k$ But it is not correct:

let order of notifitions be $b,c,.....$

($c,b..$ is the same and the other are suboptimal)

• Notification for the subroot of $b$ will stop at $0+(1+k)=1+k$ (time=0)
• Notification for the subroot of $c$ will stop at $1 + (1+k)=2+k$ (time=1)
• We don't really care about other leaves(they will all be notified by $k$)

This is different than the output to your algorithm. The approach that FrankW proposed is the correct one!