Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective
  Identifying and controlling bias is a key problem in empirical sciences.
Causal diagram theory provides graphical criteria for deciding whether and how
causal effects can be identified from observed (nonexperimental) data by
covariate adjustment. Here we prove equivalences between existing as well as
new criteria for adjustment and we provide a new simplified but still
equivalent notion of d-separation. These lead to efficient algorithms for two
important tasks in causal diagram analysis: (1) listing minimal covariate
adjustments (with polynomial delay); and (2) identifying the subdiagram
involved in biasing paths (in linear time). Our results improve upon existing
exponential-time solutions for these problems, enabling users to assess the
effects of covariate adjustment on diagrams with tens to hundreds of variables
interactively in real time.
