Almost Optimal Intervention Sets for Causal Discovery
  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.
