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:
- We require that all subgraphs generated will have the same height( max length of longest path)
- Nodes of each subgraph should be reachable from the sources within that subgraph, using nodes of that subgraph as intermediate nodes.
- 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).
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
