# Partitioning DAG into Paths

What bounds (lower or upper) are known about the complexity of partitioning a Directly 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. represent a Partially Ordered Set (poset) $P$ of width $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 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.. 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$).

• 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 (in time $n^{2.5}$) which approximates the minimal entropy. – Jeremy Aug 20 '13 at 13:30
• comment->answer? – Sasho Nikolov Aug 20 '13 at 16:11
• @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. – Jeremy Aug 21 '13 at 14:24
• 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 Aug 22 '13 at 3:35
• @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. – Jeremy Aug 22 '13 at 9:44