The causal relationships among a set of random variables are commonly
represented by a Directed Acyclic Graph (DAG), where there is a directed edge
from variable $X$ to variable $Y$ if $X$ is a direct cause of $Y$. From the
purely observational data, the true causal graph can be identified up to a
Markov Equivalence Class (MEC), which is a set of DAGs with the same
conditional independencies between the variables. The size of an MEC is a
measure of complexity for recovering the true causal graph by performing
interventions. We propose a method for efficient iteration over possible MECs
given intervention results. We utilize the proposed method for computing MEC
sizes and experiment design in active and passive learning settings. Compared
to previous work for computing the size of MEC, our proposed algorithm reduces
the time complexity by a factor of $O(n)$ for sparse graphs where $n$ is the
number of variables in the system. Additionally, integrating our approach with
dynamic programming, we design an optimal algorithm for passive experiment
design. Experimental results show that our proposed algorithms for both
computing the size of MEC and experiment design outperform the state of the
art.

该研究提出了一种在给定干预结果的情况下高效迭代可能的 Markov 等价类的方法，结合动态规划实现了最优算法，可用于计算 MEC 的大小和实验设计。实验结果表明，该方法在计算 MEC 和实验设计方面优于现有技术。