SupplementaryMaterial

The proof follows from Lemma 1. Lemma 2. Let G be a PAGn-representing a causal DAGD. We refer to the proof for the anytime FCI algorithm (Spirtes, 2001). Let the true underlying DAG beD(O,L,S), and G be the graph returned after an ICD iteration. The first ICD iterationr = 0 is trivial, where every pair of nodes is tested for marginalindependence (ICDisinitialized withacomplete graph). Let A B|[Z] S in D, such that|Z| = 1 (a single-node set).