Supplementary Material: Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias

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 Zis 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 ΠB(A,Z) such that, (a) |ΠB(A,Z)| r and (b) every node on ΠB(A,Z) is in Z, and 3. Z Z, node Z is a possible ancestor of Aor B (not a necessary condition). Denote A,B a pair of nodes from O that are connected in G and disconnected in D, and such that Ais not an ancestor of B in D. If A B |[Z0] S, where Z0 O is a minimal separating set having size n+ 1, then there exists a subset Z O having the same size of n+ 1 such that that A B |Z S, and for every node Z Zthere exists a PDS-path ΠB(A,Z) in G, such that every node V on the PDS-path is also in Z. Proof. It was previously shown that a minimal separating set for Aand B, where Ais 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).