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.)

Assume following about the graph G(V,E):

  1. We try to solve the problem for graphs in which such partition exists - if the partition doesn't exist it can be stated that it is impossible to create partition
  2. All the graph's node will have $\forall v \in V\ $ in_deg(v)=2 or in_deg(v)=1

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).


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

  • 1
    $\begingroup$ @Yakov: do you mean that each subgraph must be 'weakly connected' (connected if you replace directed edges with undirected edges) but does not have to be 'strongly connected' (there does not necessarily exist a directed path between any two vertices)? Also: by 'leaves' do you mean vertices with out-degree of zero (also known as 'sinks')? $\endgroup$ – Niel de Beaudrap Oct 5 '10 at 15:00
  • 1
    $\begingroup$ @Yakov: It is much clearer now. Just a few questions: 1) haven't you confused sources & mixes? since you said edges are directed upwards, nodes [#10,...23] must be sources rather than sinks. 2) What do you mean by "approximately"? what accuracy is required? 3) how many subgraphs should the algorithm find? Apparently, trivially outputting 1 subgraph satisfies all the requirements! $\endgroup$ – M.S. Dousti Oct 6 '10 at 18:55
  • 1
    $\begingroup$ this was just crossposted on MO: mathoverflow.net/questions/41376/… $\endgroup$ – Suresh Venkat Oct 7 '10 at 8:21
  • 1
    $\begingroup$ 1. Your example has the nodes of each subgraph being reachable from the sources within that subgraph, using nodes of that subgraph as intermediate nodes. Is that a requirement? If so please edit your question to reflect that. 2. Is the height of a subgraph the max length of longest path or max length of shortest path? $\endgroup$ – Warren Schudy Oct 9 '10 at 13:34
  • 1
    $\begingroup$ Can you tell us why you care about this problem? That way we might answer the question you really care about rather than a long sequence of questions that are close to the one you want answered. $\endgroup$ – Warren Schudy Oct 9 '10 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.