2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 26 at 6:13
  • $\begingroup$ @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? $\endgroup$ – Mengfan Ma Jul 28 at 2:45
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 28 at 5:07
  • $\begingroup$ I've been working on the reduction for hours but ...... I failed :( Could you shed some light on it? $\endgroup$ – Mengfan Ma Jul 28 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.