## Abstract

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.

Original language | English |
---|---|

Pages | 135-138 |

Number of pages | 4 |

Publication status | Published - 2019 |

Event | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization - University of Twente, Enschede, Netherlands Duration: 01.07.2019 → 03.07.2019 Conference number: 159391 |

### Conference

Conference | 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization |
---|---|

Abbreviated title | CTW 2019 |

Country/Territory | Netherlands |

City | Enschede |

Period | 01.07.19 → 03.07.19 |

## DFG Research Classification Scheme

- 4.43-01 Theoretical Computer Science