I am trying to solve this problem: Given n nodes, I need to insert edges to form topologically sorted DAG kind of situation. Each node should be able to reach any downstream node via either 1 hop or 2 hop path (not longer). I have use theta(nlogn) edges at most to do this. How do I do it?
Example for n=3:
The given clue is to use divide and conquer. If there are n nodes, and if we assume n/2 of the first half already has this property and last n/2 also has this property, how to combine these two halves so that n nodes will have this property? The property is if i and j both belong to the same half, we can get from i to j in at most 2 hops.Show how to add theta(n) additional edges so that if i is in the first half and j is in the second half we can get from i to j using only two edges.
How do I do it? I tried to connect the leaves of the first half to every node of the lowest half, then did the same with the grandparents of the leaves and so on. But that uses (n/4)*n, which is quadratic.
A simple solution would be to take the sink node (A node with 0 out-going edges, there should only be one if building a DAG using this approach) from the first half and add a directed edge from there to all the nodes in the second half. This amounts to adding n/2 edges. Then, take all the ancestors of this sink node (all other nodes in the first half) and add an edge from them to the sink node. This will be another (n/2)-1 edges totalling to a linear number of additional edges.
From the induction hypothesis the second half, as well as the first, will already have the 2 hop property. All nodes from the first half will also be 2 hops away to every node in the second half. This path will be from any first half node to the original sink node and then to any node in the second half. We now have a new DAG which combines the 2 DAGs, keeps the 2 hop property, and has a single sink node.
The analysis of this algorithm is similar to that of merge sort. We split the problem into 2 recursive sub-problems and there is a linear step combining the results. This forms the same recurrence relation as merge-sort and gives us our overall nlogn complexity.