Hello
Given a DAG with |V| = n and has s sources we have to present subgraphs such that each subgraph has approximately k1=√|s| sources and approximately k2=√|n| nodes.
If we define the height of the DAG to be the maximum path length from some source to some sink.
We require that all subgraphs generated will have approximately the same height.
The intersection of each pair of node Sets (of subgraphs) is empty.
You can see in attached picture the example of right partition(each edge in the graph is directed upwards).
There are 36 nodes and 8 sinks [#10,11,12,13,20,21,22,23]in the example .So each subgraph should have 6 nodes and 2 or 3 sinks.
Do you have idea for algorithm?
Thank you very much