<p>An <a href="https://en.wikipedia.org/wiki/Acyclic_orientation" rel="nofollow noreferrer">acyclic orientation</a> 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:</p>

<blockquote>
  <p>A <em>v-structure</em> is a three-vertex <strong>induced subgraph</strong> of a DAG like <span class="math-container">$a\rightarrow b\leftarrow c$</span>. Given an undirected and connected chordal graph <span class="math-container">$G$</span>, count the number of acyclic orientations in which no v-structure occurs.</p>
</blockquote>

<p>I was wondering if there are any commonly used techniques or algorithms to deal with:</p>

<ol>
<li>the general acyclic orientation problem;</li>
<li>acyclic orientation under some special constraint such as no local structure can occur.</li>
</ol>

<p>Any information you can provide me would be greatly appreciated.</p>

CC BY-SA 4.0
2019-07-26T06:13:31.063Z
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.
CC BY-SA 4.0
2019-07-28T02:45:41.803Z
@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?
Mengfan Ma
CC BY-SA 4.0
2019-07-28T05:07:32.573Z
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.
<reference-request><graph-theory><graph-algorithms><directed-acyclic-graph>
Common techniques for the acyclic orientation problem under some special constraint?
Mengfan Ma
# Common techniques for the acyclic orientation problem under some special constraint?

(Asked by: username_0 on 2019-07-26)

An [acyclic orientation](https://en.wikipedia.org/wiki/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.

**Tags:** reference-request, graph-theory, graph-algorithms, directed-acyclic-graph
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_1**: 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.  

---

## 0 answers

