Enumerating the directed acyclic graphs (DAGs) of a Markov equivalence class
(MEC) is an important primitive in causal analysis. The central resource from
the perspective of computational complexity is the delay, that is, the time an
algorithm that lists all members of the class requires between two consecutive
outputs. Commonly used algorithms for this task utilize the rules proposed by
Meek (1995) or the transformational characterization by Chickering (1995), both
resulting in superlinear delay. In this paper, we present the first linear-time
delay algorithm. On the theoretical side, we show that our algorithm can be
generalized to enumerate DAGs represented by models that incorporate background
knowledge, such as MPDAGs; on the practical side, we provide an efficient
implementation and evaluate it in a series of experiments. Complementary to the
linear-time delay algorithm, we also provide intriguing insights into Markov
equivalence itself: All members of an MEC can be enumerated such that two
successive DAGs have structural Hamming distance at most three.

提出了一种线性时间延迟算法，用于枚举由 Meek 和 Chickering 规则产生的马尔可夫等价类中的有向无环图，并在实验中评估其有效性，同时向马尔可夫等价本身提供了新的见解。