An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation

In a previous paper [Pearl and Verma, 1991] we presented an algorithm for\nextracting causal influences from independence information, where a causal\ninfluence was defined as the existence of a directed arc in all minimal causal\nmodels consistent with the data. In this paper we address the question of\ndeciding whether there exists a causal model that explains ALL the observed\ndependencies and independencies. Formally, given a list M of conditional\nindependence statements, it is required to decide whether there exists a\ndirected acyclic graph (dag) D that is perfectly consistent with M, namely,\nevery statement in M, and no other, is reflected via dseparation in D. We\npresent and analyze an effective algorithm that tests for the existence of such\na day, and produces one, if it exists.\n