An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). I've recently encountered a problem in the field of machine learning(Bayesian network), which turns out to be a special case of the acyclic orientation problem:
A v-structure is a three-vertex induced subgraph of a DAG like $a\rightarrow b\leftarrow c$. Given an undirected and connected chordal graph $G$, count the number of acyclic orientations in which no v-structure occurs.
I was wondering if there are any commonly used techniques or algorithms to deal with:
- the general acyclic orientation problem;
- acyclic orientation under some special constraint such as no local structure can occur.
Any information you can provide me would be greatly appreciated.