# A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models

arXiv: https://arxiv.org/abs/1302.3600 · HTML: https://mlsanity.com/paper/1302.3600/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2013.

## Built on by (most cited first, 7 of 7)

- [Causal Modeling with Stationary Diffusions](https://mlsanity.com/paper/2310.17405/) (2023)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Establishing Markov Equivalence in Cyclic Directed Graphs](https://mlsanity.com/paper/2309.03092/) (2023)
- [Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models](https://mlsanity.com/paper/2509.21423/) (2025)
- [Learning Large Causal Structures from Inverse Covariance Matrix via Sparse Matrix Decomposition](https://mlsanity.com/paper/2211.14221/) (2022)
- [Learning Personalized Brain Functional Connectivity of MDD Patients from Multiple Sites via Federated Bayesian Networks](https://mlsanity.com/paper/2301.02423/) (2023)
- [Lower Bounds on the Size of Markov Equivalence Classes](https://mlsanity.com/paper/2506.20933/) (2025)

## Abstract (arXiv)

Although the concept of d-separation was originally defined for directed acyclic graphs (see Pearl 1988), there is a natural extension of he concept to directed cyclic graphs. When exactly the same set of d-separation relations hold in two directed graphs, no matter whether respectively cyclic or acyclic, we say that they are Markov equivalent. In other words, when two directed cyclic graphs are Markov equivalent, the set of distributions that satisfy a natural extension of the Global Directed Markov condition (Lauritzen et al. 1990) is exactly the same for each graph. There is an obvious exponential (in the number of vertices) time algorithm for deciding Markov equivalence of two directed cyclic graphs; simply chech all of the d-separation relations in each graph. In this paper I state a theorem that gives necessary and sufficient conditions for the Markov equivalence of two directed cyclic graphs, where each of the conditions can be checked in polynomial time. Hence, the theorem can be easily adapted into a polynomial time algorithm for deciding the Markov equivalence of two directed cyclic graphs. Although space prohibits inclusion of correctness proofs, they are fully described in Richardson (1994b).