Is there any known work on generating random uniformly distributed DAGs given a set of path existence/absence constraints?

Question

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,

George

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

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.