Supplementary Material: Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias Shami Nisimov Intel Labs Gal Novik Intel Labs

In this section we provide a detailed proof for the correctness and completeness of the ICD algorithm. For easier referencing we describe ICD in Algorithm 1, and describe the ICD-Sep conditions. A set Z is a subset of ICD-Sep(A, B) given r {0,..., |O| 2}, if and only if 1. |Z| = r, 2. Z Z, there exists a PDS-path Π Let G be a PAG n-representing DAG D(O, S, L). Denote A, B a pair of nodes from O that are connected in G and disconnected in D, and such that A is not an ancestor of B in D. If A B | [Z It was previously shown that a minimal separating set for A and B, where A is not an ancestor of B, is a subset of D-Sep(A, B) (Spirtes et al., 2000, page 134 and Theorem 6.2; Spirtes et al., 1999). By definition, a node Z is in D-Sep(A, B) if and only if in the MAG there is a path between A and Z such that every node, except for the end points, is: 1. a collider and 2. an ancestor of A or B. Denote such path DS-Path (an inducing path for L, S).