I have the following problem:

Given a set of path existence/absence constraints C (not necessarily for all pairs of vertices) and a (fixed) set of vertices V, generate a random DAG, s.t.

  • it is acyclic (by definition),
  • it contains all vertices of V,
  • all constraints in C hold,
  • each possible DAG (given the specific constraints) should be generated with equal probability.

The type of the constraints should be self-explanatory, but in case it is not I can edit the question to provide additional information.

Intuitively I would say that the problem should be NP-hard.

The question is:

Are there any known results on this problem?

Thanks in advance,


Edit: added "(not necessarily for all pairs of vertices)" in the problem definition.


1 Answer 1


There is some work concerning random orders. Good and slightly outdated survey is $[1]$. In this survey you can find description for the basic models of random orders: uniform model, model of random graphs orders and model of random $k$-dimensional orders. It should be noted that these models are derived for arbitrary random orders and maybe you won't find there results on generation of random orders which are extensions of the given partial order.

  1. Brightwell G. Models of Random Partial Orders. Surveys in combinatorics, 1993.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.