  We initiate the study of counting Markov Equivalence Classes (MEC) under
logical constraints. MECs are equivalence classes of Directed Acyclic Graphs
(DAGs) that encode the same conditional independence structure among the random
variables of a DAG model. Observational data can only allow to infer a DAG
model up to Markov Equivalence. However, Markov equivalent DAGs can represent
different causal structures, potentially super-exponentially many. Hence,
understanding MECs combinatorially is critical to understanding the complexity
of causal inference. In this paper, we focus on analysing MECs of size one,
with logical constraints on the graph topology. We provide a polynomial-time
algorithm (w.r.t. the number of nodes) for enumerating essential DAGs (the only
members of an MEC of size one) with arbitrary logical constraints expressed in
first-order logic with two variables and counting quantifiers (C^2). Our work
brings together recent developments in tractable first-order model counting and
combinatorics of MECs.
