Rooted Tree and Greedy Algorithms

Question

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send the message to all nodes. for each node v, d(v) and c(v) shows the distance v to it's deepest leaf and number of it's childs. i propose two greedy algorithm, but i couldent find any prove or counterexample.

1) each node that recive a message, in each step send a message to one of childeren taht has a maximum d(v).

2) each node that recive a message, in each step send a message to one of childeren taht has a maximum c(v).

anyone could help me?

Answer 1

Actually 1) can be used to find a counter-example to 2), and vice-versa.

Take tree $T$ with the root having two child subtrees $T_1, T_2$. $T_1$ is a node with many leaf children (say 10), and $T_2$ is a path of small length (say 2). You want to send the message to $T_1$ first, as $T_2$ will finish first even if receives the message second. Thus 1) won't work.

To show that 2) won't work, set $T_1$ as a node with two leaf children (a cherry), and $T_2$ as a path of large length. You want to send the message to the path first, even though its root has less children than $T_1$.

What I suggest is some kind of dynamic programming algorithm. For some internal node $v$, denote by $time(v)$ the minimum number of iterations needed to pass all messages to the $v$ subtree. Say $v$ has children $v_1, \ldots, v_k$. If you can find out how to compute $time(v)$ as a function of $time(v_1), \ldots, time(v_k)$, you can pass the message to the most time-consuming child (that hasn't had the message yet) at every iteration.

Answer 2

Both the greedy algorithms are wrong. Possible counterexamples are:

1. A tree in which the maximum depth $max[d(v_i)]$ is smaller than maximum no. of children $max[d(c_i)]$.
2. A tree in which the maximum depth $max[d(v_i)]$ is greater than maximum no. of children $max[d(c_i)]$.

A possible algorithm that comes to mind is the following: Start with the lowest level. Since these are leaves, give them a score of $s_i = d(v_i)$. In fact all leaves get this score. Now move a level up and give a score of $s_i = c_i + max\{s_{j_1},s_{j_2},\ldots ,s_{j_{c_i}}\}$. After you given scores to all vertices, the min. time it takes to transmit message to all is the score of the root.

Answer 3

The result of createSchedule is a list of rounds. Each round is described by nodes receiving message from their parent that round. Each parent can only send one message per round.

public class Scheduler {


@Override
public List<Collection<Node>> createSchedule(Node root) {
    List<Collection<Node>> result = new ArrayList<>();

    // map will hold pairs of <nodeId, count of iterations required for subtree of node>
    HashMap<Integer, Integer> countOfIterationsRequiredForNode = new HashMap<Integer, Integer>();

    // map will hold pairs of <nodeId, children ordered by sending order>
    HashMap<Integer, Node[]> nodesInSendingOrder = new HashMap<Integer, Node[]>();

    // computes the count of required iterations for root and each node in its subtree
    computeRequiredIterationsAndChildOrder(root, countOfIterationsRequiredForNode, nodesInSendingOrder);

    // in 0 iterations only root has got the message
    result.add(Collections.singletonList(root));

    // prepare the schedule
    int iterationCounter = 0;
    while (result.size() > iterationCounter) {
        Collection<Node> nodesToStartSendingInIteration = result.get(iterationCounter);
        for (Node n : nodesToStartSendingInIteration) {
            int offset = 1;
            if (nodesInSendingOrder.get(n.getId()) == null) {
                // no children to send this message to
                continue;
            }
            for (Node childNode : nodesInSendingOrder.get(n.getId())) {
                // add each children into iteration where it belongs
                int iterationWhenChildrenGetsMessage = iterationCounter + offset;
                if (result.size() <= iterationWhenChildrenGetsMessage) {
                    result.add(new HashSet<Node>());
                }
                result.get(iterationWhenChildrenGetsMessage).add(childNode);
                offset++;
            }
        }
        iterationCounter++;
    }

    return result;
}


/**
 * @param parentNode {@link Node} for which we are computing required iterations count
 * @param countOfIterationsRequiredForNode help structure to store computed iterations count
 * @param nodesInSendingOrder help structure to store optimal children ordering
 */
private void computeRequiredIterationsAndChildOrder(Node parentNode, final HashMap<Integer, Integer> countOfIterationsRequiredForNode,
        HashMap<Integer, Node[]> nodesInSendingOrder) {

    if (parentNode.getChildren().isEmpty()) {
        // leaf. no more iterations are required after this node receives the message
        countOfIterationsRequiredForNode.put(parentNode.getId(), Integer.valueOf(0));
        return;
    }

    // children need to be processed before computing this node
    for (Node childNode : parentNode.getChildren()) {
        computeRequiredIterationsAndChildOrder(childNode, countOfIterationsRequiredForNode, nodesInSendingOrder);
    }

    nodesInSendingOrder.put(parentNode.getId(), parentNode.getChildren().toArray(new Node[] {}));
    Arrays.sort(nodesInSendingOrder.get(parentNode.getId()), new Comparator<Node>() {

        @Override
        public int compare(Node node1, Node node2) {
            Integer iterationsNode1 = countOfIterationsRequiredForNode.get(node1.getId());
            Integer iterationsNode2 = countOfIterationsRequiredForNode.get(node2.getId());
            return iterationsNode2.compareTo(iterationsNode1);
        }

    });

    // nodes are ordered by required number of iteration, descending order
    Node[] orderedChildren = nodesInSendingOrder.get(parentNode.getId());

    // compute required iterations depending on children
    int extraIterationsForParentNode = 0;
    int extraIterationsBeforeReachingLastSibling = orderedChildren.length - 1;
    for (Node child : orderedChildren) {
        Integer iterationsChild = countOfIterationsRequiredForNode.get(child.getId());
        extraIterationsForParentNode = Math.max(extraIterationsForParentNode, iterationsChild - extraIterationsBeforeReachingLastSibling);
        extraIterationsBeforeReachingLastSibling--;
    }

    countOfIterationsRequiredForNode.put(parentNode.getId(), Integer.valueOf(orderedChildren.length + extraIterationsForParentNode));

}

}