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.