Corrigendum to “Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework” [Artif. Intell. 270 (2019) 1–40, (S0004370219300025), (10.1016/j.artint.2018.12.006)]

This Corrigendum reports an error found in Lemma 2 [1, page 8] which states that the augmented graph [Formula presented] can be computed in time [Formula presented]. In the proof of the lemma, we argue that all four steps of the algorithm presented in the proof can be performed in time [Formula presented], which is not true. Step 4, “for each component, identify all its parents and link them all by undirected edges in [Formula presented]”, requires [Formula presented] time in the worst-case.¹ [Formula presented] So, the correct statement should be as follows: Given an AG [Formula presented], the augmented graph [Formula presented] can be computed in time [Formula presented]. In consequence, the statements in Proposition 3 and Proposition 4 should be corrected as well and the claims should be read as follows: Proposition 3 Using the algorithm above, the task TESTMINSEP, both for testing I-minimality and strong-minimality, can be solved in time [Formula presented]. Proposition 4 The algorithm above finds an I-minimal m-separator Z, with [Formula presented], in time [Formula presented]. The propositions are summarized in Table 2 and Table 4, which also show the incorrect run-time. Meanwhile, both propositions have become obsolete since our follow up paper [2] introduces a new algorithm that can solve the tasks of Propositions 3 and 4 in time [Formula presented], where n denotes the number of nodes and m the number of edges in a causal structure. We thank Marcel Wienöbst for pointing out the error in our run-time analysis in the proof of Lemma 2.