Efficient Enumeration of Markov Equivalent DAGs*

NEW

Problem: Reconstructed statement: Given a CPDAG $G$ with $n$ vertices and $m$ adjacencies, produce all DAGs in its Markov equivalence class $[G]$ exactly once in an order

$$D_1,D_2,\ldots,D_N$$

such that $\operatorname{SHD}(D_i,D_{i+1})\le 3$, improving the $O(m^2)$-delay implementation of the DFS construction used for Theorem 6 of Wienöbst–Luttermann–Bannach–Liśkiewicz. Here SHD counts a covered edge reversal as distance one, as in the paper.

Result: The open problem has a positive resolution under the standard word-RAM/dynamic-dictionary model.

There is an exact algorithm with delay

$$O(n+m\log n),$$

and with randomized incremental hashing this becomes expected

$$O(n+m).$$

Thus the $O(m^2)$ lookup bottleneck is not inherent.

Sketch of the exact algorithm. Consider the graph $\Gamma$ whose vertices are DAGs in $[G]$, with an edge between two DAGs if one is obtained from the other by reversing a covered edge. By Chickering’s theorem, $\Gamma$ is connected. Run DFS on $\Gamma$, but output a DAG on entry if its DFS depth is even and on exit if its DFS depth is odd. The standard DFS parity argument gives that consecutive outputs are at tree-distance at most $3$, hence have SHD at most $3$.

The improvement is data-structural. Store each DAG by a canonical persistent bit-vector over the $m$ skeleton edges. Flipping one edge costs $O(\log m)$, and equality of DAGs is pointer equality. Store the visited set by these canonical roots, so membership is $O(1)$. Also store each parent set $\operatorname{Pa}_D(v)$ as a canonical persistent set. Then a directed edge $u\to v$ is covered iff

$$\operatorname{Pa}_D(v)\setminus\{u\}=\operatorname{Pa}_D(u),$$

which is tested by one persistent deletion and pointer comparison in $O(\log n)$.

Between two parity-DFS outputs only constantly many DFS-tree moves occur, and at each such state at most $m$ candidate edges are scanned. Hence the delay is

$$O(n+m\log n),$$

including the $O(n+m)$ cost of writing the output DAG. Correctness follows because covered reversals preserve Markov equivalence, DFS reaches all of $[G]$, visited roots prevent duplicates, and the parity traversal gives SHD at most $3$.

Verification audit: the statement matches the paper’s Theorem 6 sequence problem; no extra graph-theoretic assumptions are added beyond $G$ being a CPDAG; the computational model is stated explicitly; Chickering’s covered-edge theorem applies at every reversal; and the conclusion is exactly a better delay bound for producing an SHD-$\le 3$ enumeration.

Citation: Uses Chickering’s covered-edge characterization: D. M. Chickering, “A transformational characterization of equivalent Bayesian network structures,” UAI 1995. The open problem appears in Wienöbst, Luttermann, Bannach, Liśkiewicz, “Efficient Enumeration of Markov Equivalent DAGs,” arXiv:2301.12212. No published source known to me gives the above data-structural improvement.