Question

Hello

Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes.

(Note: Approximately means that each subgraph contains $\lceil \sqrt{n}\rceil$ or $\lfloor \sqrt{n} \rfloor$ nodes and covers $\lceil \sqrt{s}\rceil$ or $\lfloor \sqrt{s} \rfloor$ sourses of the original graph. All sources of the original graph have to be covered by some subgraph, so there has to be $\lceil \sqrt{s}\rceil$ or $\lfloor \sqrt{s} \rfloor$ subgraphs.)

Let's define the height of the DAG to be the maximum path length from some source to some sink.

The subgraphs have following requirements:

1. We require that all subgraphs generated will have the same height( max length of longest path)
2. Nodes of each subgraph should be reachable from the sources within that subgraph, using nodes of that subgraph as intermediate nodes.
3. Moreover, the intersection of each pair of node sets (of subgraphs) must be empty.

In the following picture, you can see an example of a right partition (assume that each edge in the graph is directed upwards).

http://i.imgur.com/PSaBI.png

There are 36 nodes and 8 sources [#10,11,12,13,20,21,22,23] in the example. So each subgraph should have 6 nodes and 2 or 3 sources.

Do you have idea for algorithm?

Thank you very much