# Efficient algorithm to enumerate all member DAGs of a Markov equivalence class

I'm working on a research project involving Bayesian networks. BNs are directed acyclic graphs (DAGs) used to compactly represent joint distributions of variables. In many cases, multiple DAGs can represent the same distribution, and so compose an equivalence class. Equivalent DAGs share the same skeleton (same edges if one ignores direction), and the orientation of edges in their v-structures (X->Y, Z->Y, but no edge between X and Z) must be the same. Such equivalence classes can be represented by partially directed acyclic graphs (PDAGs), with the compelled (i.e. have the same orientation) edges directed and the reversible edges undirected.

Given a DAG, I would like to be able to find all other DAGs in its equivalence class. I'm aware of an efficient algorithm (Chickering 1995) that, given a DAG, finds the complete PDAG representing its equivalence class. I'm also aware of an algorithm (Dor and Tarsi 1992) that, given a PDAG, generates a random member DAG of the equivalence class. I am not interested in a random member, but rather in enumerating all members.

It might seem trivial at first glance--why not just try all combinations of orientations of the reversible edges, and discard the ones that aren't acyclic? But the number of possibilities grows exponentially in the number of reversible edges, so I'm worried that this won't work for large graphs. I've seen some sources claim that the proportion of edges that are reversible is relatively small, but still, if the graph is large enough, it will still be problematic. I'm working with graphs of up to several hundred variables, with several thousand being a possibility later on.

• Is there some way you could avoid doing this? For example, Maathuis et al. (2009) started with a problem that looked like it would require enumerating all of the DAGs, and showed that it could be solved by finding all possible parent sets of each node. They were also motivated by a high-dimensional problem (5,000 nodes). What is the problem you are trying to solve using the list of DAGs? – Lizzie Silver Oct 16 '14 at 15:26
• A way to do this is the following: pick any undirected edge, try both orientations and recurse. After applying an orientation of an edge, apply Meek's rules to propagate changes (arxiv.org/ftp/arxiv/papers/1302/1302.4972.pdf). – George Oct 19 '14 at 22:50