We conjecture that the worst case number of experiments necessary and
sufficient to discover a causal graph uniquely given its observational Markov
equivalence class can be specified as a function of the largest clique in the
Markov equivalence class. We provide an algorithm that computes intervention
sets that we believe are optimal for the above task. The algorithm builds on
insights gained from the worst case analysis in Eberhardt et al. (2005) for
sequences of experiments when all possible directed acyclic graphs over N
variables are considered. A simulation suggests that our conjecture is correct.
We also show that a generalization of our conjecture to other classes of
possible graph hypotheses cannot be given easily, and in what sense the
algorithm is then no longer optimal.

本文研究探讨了在给定一个观测 Markov 等价类的因果图时，发现其唯一性所需的最坏情况实验次数可以指定为 Markov 等价类中最大团的函数。我们提供了一种算法来计算我们认为对于上述任务最优的干预集合。该算法建立在 Eberhardt 等人（2005 年）对于当考虑所有可能的 N 个变量的有向无环图时的一系列实验的最坏情况分析中获得的洞见的基础上。仿真结果表明我们的猜想是正确的。我们还展示了我们的猜想推广到其他可能的图假设类别不易进行，以及算法不再最优的意义。