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$?


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

  • 3
    $\begingroup$ 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. $\endgroup$
    – Jeremy
    Aug 20 '13 at 13:30
  • 2
    $\begingroup$ comment->answer? $\endgroup$ Aug 20 '13 at 16:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jeremy
    Aug 21 '13 at 14:24
  • $\begingroup$ 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. $\endgroup$ Aug 22 '13 at 3:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jeremy
    Aug 22 '13 at 9:44

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.