1
$\begingroup$

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:

Tree example

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:

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?

$\endgroup$
  • 1
    $\begingroup$ Try to prove that your algorithm works instead of asking us to provide you with a counterexample. $\endgroup$ – Yuval Filmus Oct 24 '15 at 12:27
2
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.