Given DAG with | V | = n and has s sources, we must present such subgraphs that each subgraph has approximately k1 = √ | s | sources and approximately k2 = √ | n | nodes.
If we define the DAG height as the maximum path length from some source to some receiver.
We require all subgraphs created to be approximately the same height.
The intersection of each node pair. The set (subgraphs) is empty.
In the attached figure, you can see an example of the right section (each edge in the graph is directed up).
In the example, there are 36 nodes and 8 drains [# 10,11,12,13,20,21,22,23]. Each subgraph should have 6 nodes and 2 or 3 receivers.
Do you have an idea for an algorithm?
Many thanks