  Maximal ancestral graphs (MAGs) have many desirable properties; in particular
they can fully describe conditional independences from directed acyclic graphs
(DAGs) in the presence of latent and selection variables. However, different
MAGs may encode the same conditional independences, and are said to be
\emph{Markov equivalent}. Thus identifying necessary and sufficient conditions
for equivalence is essential for structure learning. Several criteria for this
already exist, but in this paper we give a new non-parametric characterization
in terms of the heads and tails that arise in the parameterization for discrete
models. We also provide a polynomial time algorithm ($O(ne^{2})$, where $n$ and
$e$ are the number of vertices and edges respectively) to verify equivalence.
Moreover, we extend our criterion to ADMGs and summary graphs and propose an
algorithm that converts an ADMG or summary graph to an equivalent MAG in
polynomial time ($O(n^{2}e)$). Hence by combining both algorithms, we can also
verify equivalence between two summary graphs or ADMGs.
