Verification and search algorithms for causal DAGs

We study two problems related to recovering causal graphs from interventional data: (i) verification, where the task is to check if a purported causal graph is correct, and (ii) search, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of covered edges, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs.