Graphical methods for finding instrumental variables

Instrumental variables (IVs) are a popular approach to identify causal effects. For valid inference, IVs must not be direct causes of any variable in the model except the explanatory variable X. Such variables do not exist in many model instances, so the approach has been generalized to conditional IVs. However, a barrier for application of this method is of algorithmic nature: So far, it was not clear whether such conditional IVs can be tested and found efficiently. We prove that it is indeed an NPcomplete problem to test if a given variable is a conditional IV. However, if the covariates are restricted to ancestors, this test can be performed in linear time. This implies a new definition of IVs, which we term ancestral IVs. It turns out that an ancestral IV exists if and only if a conditional IV exists in a graph. We use this definition to obtain efficient algorithms to find conditional IVs.