<p>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.</p>

<p>(Note: <strong>Approximately</strong> 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 <strong>sources</strong> 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.)</p>

<p>Assume following about the graph G(V,E):</p>

<ol>
<li>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</li>
<li>All the graph's node will have $\forall v \in V\ $ in_deg(v)=2 or in_deg(v)=1</li>
</ol>

<p>Let's define the <strong>height</strong> of the DAG to be the maximum path length from some source to some sink.</p>

<p>The subgraphs have following requirements:</p>

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

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

<p><img src="https://i.sstatic.net/PSaBI.png" alt="illustration"></p>

<p>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.</p>

<p>Do you have idea for algorithm?</p>

<p>Thank you very much </p>

CC BY-SA 2.5
2010-10-05T10:10:18.827Z
By "it is forbidden that the subgraph consists two parts which don't share any common node," do you mean that the subgraph is connected?
Sadeq Dousti
CC BY-SA 2.5
2010-10-05T10:13:49.517Z
It can be supposed that it is indirectly connected
YAKOVM
CC BY-SA 2.5
2010-10-05T12:23:41.443Z
Perhaps it's my misunderstanding. Could you give an example? An illustration will certainly help.
Sadeq Dousti
CC BY-SA 2.5
2010-10-05T15:00:24.977Z
@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')?
Niel de Beaudrap
CC BY-SA 2.5
2010-10-05T17:20:52.413Z
1,yes it is weakly-connected
2.leaves are vertices with in degree zero
YAKOVM
CC BY-SA 2.5
2010-10-06T10:46:51.117Z
Digraph contains atleast $\sqrt{|V|}$ leaves
YAKOVM
CC BY-SA 2.5
2010-10-06T16:22:21.380Z
(1) Is |V| required to be a perfect square?  If not, what do you mean by “every subgraph will include $k=\sqrt{|V|}$ leaves”?  (2) Vertices with in-degree 0 are usually called sources.  (3) Please update the question so that people do not have to follow the discussion in the comments to understand the question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-06T17:20:15.103Z
I rewrote the question I hope its OK now
YAKOVM
CC BY-SA 2.5
2010-10-06T18:55:46.983Z
@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!
Sadeq Dousti
CC BY-SA 2.5
2010-10-06T21:30:57.537Z
@Sadeq I have fixed my post I hope its clear now if not tell me
YAKOVM
CC BY-SA 2.5
2010-10-07T06:03:38.743Z
@Yakov: the question seems **much** clearer now, thanks.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-07T08:21:08.680Z
this was just crossposted on MO: http://mathoverflow.net/questions/41376/digraphdag-partitioning-to-subgraphs
Suresh Venkat
CC BY-SA 2.5
2010-10-09T13:34:57.510Z
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?
Warren Schudy
CC BY-SA 2.5
2010-10-09T15:55:09.040Z
@Warren Schudy:  I have corrected the question thank you.
YAKOVM
CC BY-SA 2.5
2010-10-09T17:54:00.930Z
Such a decomposition doesn't always exist. Consider a graph on 9 nodes labeled A through I with the following 8 arcs: A->E, B->E, C->E, D->E, E->F->G->H->I. It has 4 sources so we're looking for two subgraphs each with 2 sources and 3 nodes. This is impossible since clearly every subgraph has to include node E.
Warren Schudy
CC BY-SA 2.5
2010-10-09T17:55:01.123Z
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.
Warren Schudy
CC BY-SA 2.5
2010-10-09T18:35:32.310Z
It can be assumed that 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
YAKOVM
CC BY-SA 2.5
2010-10-09T18:36:49.607Z
Also it can be assumed that in the graphs, for which the partition should be performed , every node will have in degree = 2 or 1
YAKOVM
CC BY-SA 2.5
2010-10-10T12:37:30.957Z
I need at least some kind of idea that I should use so you could moveon.
YAKOVM
<ds.algorithms><graph-theory><graph-algorithms><directed-acyclic-graph><clustering>
DAG partitioning to subgraphs
YAKOVM
# DAG partitioning to subgraphs

(Asked by: username_0 on 2010-10-05)

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

![illustration](https://i.sstatic.net/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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, directed-acyclic-graph, clustering

> **Comments:**
> **username_1**: By "it is forbidden that the subgraph consists two parts which don't share any common node," do you mean that the subgraph is connected?  
> **username_0**: It can be supposed that it is indirectly connected  
> **username_1**: Perhaps it's my misunderstanding. Could you give an example? An illustration will certainly help.  
> **username_2**: @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')?  
> **username_0**: 1,yes it is weakly-connected 2.leaves are vertices with in degree zero  
> **username_0**: Digraph contains atleast $\sqrt{|V|}$ leaves  
> **username_3**: (1) Is |V| required to be a perfect square?  If not, what do you mean by “every subgraph will include $k=\sqrt{|V|}$ leaves”?  (2) Vertices with in-degree 0 are usually called sources.  (3) Please update the question so that people do not have to follow the discussion in the comments to understand the question.  
> **username_0**: I rewrote the question I hope its OK now  
> **username_1**: @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!  
> **username_0**: @Sadeq I have fixed my post I hope its clear now if not tell me  
> **username_2**: @Yakov: the question seems **much** clearer now, thanks.  
> **username_4**: this was just crossposted on MO: http://mathoverflow.net/questions/41376/digraphdag-partitioning-to-subgraphs  
> **username_5**: 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?  
> **username_0**: @username_5:  I have corrected the question thank you.  
> **username_5**: Such a decomposition doesn't always exist. Consider a graph on 9 nodes labeled A through I with the following 8 arcs: A->E, B->E, C->E, D->E, E->F->G->H->I. It has 4 sources so we're looking for two subgraphs each with 2 sources and 3 nodes. This is impossible since clearly every subgraph has to include node E.  
> **username_5**: 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.  
> **username_0**: It can be assumed that 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  
> **username_0**: Also it can be assumed that in the graphs, for which the partition should be performed , every node will have in degree = 2 or 1  
> **username_0**: I need at least some kind of idea that I should use so you could moveon.  

---

## 0 answers

