<p>What bounds (lower or upper) are known about the complexity of partitioning a <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="nofollow">Directly Acyclic Graph</a> (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal H}(n_1,\ldots,n_w)= n\lg n - \sum_{i=1}^w n_i \lg n_i$?</p>

<h3>Motivation</h3>

<ul>
<li><p><a href="http://www.academia.edu/2845803/Sorting_and_selection_in_posets" rel="nofollow">Daskalakis et al.</a> represent a <a href="http://en.wikipedia.org/wiki/Partially_ordered_set" rel="nofollow">Partially Ordered Set</a> (poset) $P$ of <a href="http://planetmath.org/posetheightandwidth" rel="nofollow">width</a> $w$ by $w$ chains and pointers of length $\lg n$ bits each between them. A partition such as the one described above would yield a smaller encoding of some posets?</p></li>
<li><p><a href="http://link.springer.com/chapter/10.1007%2F978-3-642-25591-5_32" rel="nofollow">Farzan and Fischer</a> presented a data-structure for posets, compressed into space depending on $n$ and $w$ and supporting many operators in constant time, inspired from the one from  <a href="http://www.academia.edu/2845803/Sorting_and_selection_in_posets" rel="nofollow">Daskalakis et al.</a>. Plugging in a nice partitioning algorithm for DAGs would yield a data structure compressed into space depending on $n$ and the entropy of the poset (a finer measure than $w$).</p></li>
</ul>

CC BY-SA 3.0
2013-08-20T13:30:46.913Z
I asked the question at the open-problem session of the conference "Canadian Conference on Computational Geometry" (CCCG). Jean Cardinal pointed out a [greedy partitioning algorithm](http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=2735C20172674D00145CFE2D9FB653E6?doi=10.1.1.248.1376) (in time $n^{2.5}$) which approximates the minimal entropy.
J.y B.y
CC BY-SA 3.0
2013-08-20T16:11:39.200Z
comment->answer?
Sasho Nikolov
CC BY-SA 3.0
2013-08-21T14:24:40.873Z
@SashoNikolov Not really: 1) the algorithm from Jean Cardinal is only approximating the minimal entropy; and 2) the complexity of the algorithm is not necessarily optinal.
J.y B.y
CC BY-SA 3.0
2013-08-22T03:35:21.450Z
What do you mean by "what is the complexity"? I thought you meant to ask if this is achievable in polynomial time or NP-hard. Unless the complexity is linear, it would be hard to claim optimality.
Sasho Nikolov
CC BY-SA 3.0
2013-08-22T09:44:20.610Z
@SashoNikolov: I meant to ask what results are known about this problem: I do not feel up-to-date in the field of graphs and I have no idea whether the problem might be NP-Hard or Polynomial, and if Polynomial, to which exponent.
J.y B.y
<directed-acyclic-graph><partition-problem><shannon-entropy>
Partitioning DAG into Paths
J.y B.y
# Partitioning DAG into Paths

(Asked by: username_0 on 2013-07-31)

What bounds (lower or upper) are known about the complexity of partitioning a [Directly Acyclic Graph](http://en.wikipedia.org/wiki/Directed_acyclic_graph) (DAG) into paths of respective sizes $n\_1,\ldots,n\_w$, such that to minimize their entropy $n{\cal H}(n\_1,\ldots,n\_w)= n\lg n - \sum\_{i=1}^w n\_i \lg n\_i$?

### Motivation

* [Daskalakis et al.](http://www.academia.edu/2845803/Sorting_and_selection_in_posets) represent a [Partially Ordered Set](http://en.wikipedia.org/wiki/Partially_ordered_set) (poset) $P$ of [width](http://planetmath.org/posetheightandwidth) $w$ by $w$ chains and pointers of length $\lg n$ bits each between them. A partition such as the one described above would yield a smaller encoding of some posets?
* [Farzan and Fischer](http://link.springer.com/chapter/10.1007%2F978-3-642-25591-5_32) presented a data-structure for posets, compressed into space depending on $n$ and $w$ and supporting many operators in constant time, inspired from the one from [Daskalakis et al.](http://www.academia.edu/2845803/Sorting_and_selection_in_posets). Plugging in a nice partitioning algorithm for DAGs would yield a data structure compressed into space depending on $n$ and the entropy of the poset (a finer measure than $w$).

**Tags:** directed-acyclic-graph, partition-problem, shannon-entropy

> **Comments:**
> **username_0**: I asked the question at the open-problem session of the conference "Canadian Conference on Computational Geometry" (CCCG). Jean Cardinal pointed out a [greedy partitioning algorithm](http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=2735C20172674D00145CFE2D9FB653E6?doi=10.1.1.248.1376) (in time $n^{2.5}$) which approximates the minimal entropy.  
> **username_1**: comment->answer?  
> **username_0**: @SashoNikolov Not really: 1) the algorithm from Jean Cardinal is only approximating the minimal entropy; and 2) the complexity of the algorithm is not necessarily optinal.  
> **username_1**: What do you mean by "what is the complexity"? I thought you meant to ask if this is achievable in polynomial time or NP-hard. Unless the complexity is linear, it would be hard to claim optimality.  
> **username_0**: @SashoNikolov: I meant to ask what results are known about this problem: I do not feel up-to-date in the field of graphs and I have no idea whether the problem might be NP-Hard or Polynomial, and if Polynomial, to which exponent.  

---

## 0 answers

