# Common techniques for the acyclic orientation problem under some special constraint?

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:

1. the general acyclic orientation problem;
2. acyclic orientation under some special constraint such as no local structure can occur.

Any information you can provide me would be greatly appreciated.

• Without the restriction that the graph be chordal, I suspect one could reduce #MONOTONE-2SAT to your problem. If so, that would prove that your problem is #P-complete. In particular, I'm thinking of the following reduction: construct a graph with one vertex per clause in the MONOTONE-2SAT instance, and an edge between two vertices if the corresponding clauses share a common variable. If I'm right, that means that any algorithm would have to somehow make use of the chordal property of G.
– D.W.
Jul 26 '19 at 6:13
• @D.W. I'm trying to do the reduction based on your suggestion. It goes like this: suppose there exists such a reduction from MONOTONE-2SAT to NON-V-DAG(my problem without chordal constraint), then for any MONOTONE-2SAT instance I, one should be able to construct a graph G for the NON-V-DAG. For each assignment A of I, an corresponding orientation o(A) of G should be obtained. If A is a truth assignment, o(A) is a non-v-structure acyclic orientation. If A is a false assignment, o(A) is an orientation with directed cycle or v-structure or both. Is my thinking correct? Jul 28 '19 at 2:45
• Yes, that's a correct statement of the definition of what it means to be a reduction. If it all works out, we would associate each edge with a variable; treat the variable as indicating the orientation of that edge; and then encode the "non-v-structure" as a 2-CNF clause. But I haven't checked whether this idea for a reduction actually works; you'd need to check the ideas. Are you comfortable with reductions? If not, this might be a challenging exercise.
– D.W.
Jul 28 '19 at 5:07