A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed
  Cyclic Graphical Models
  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).
