# Proof Supplement - Learning Sparse Causal Models is not NP-hard (UAI2013)

arXiv: https://arxiv.org/abs/1411.1557 · HTML: https://mlsanity.com/paper/1411.1557/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2014.

## Built on by (most cited first, 1 of 1)

- [Causal Inference for Chatting Handoff](https://mlsanity.com/paper/2210.02862/) (2022)

## Abstract (arXiv)

This article contains detailed proofs and additional examples related to the UAI-2013 submission `Learning Sparse Causal Models is not NP-hard'. It describes the FCI+ algorithm: a method for sound and complete causal model discovery in the presence of latent confounders and/or selection bias, that has worst case polynomial complexity of order N2(k+1) in the number of independence tests, for sparse graphs over N nodes, bounded by node degree k. The algorithm is an adaptation of the well-known FCI algorithm by (Spirtes et al., 2000) that is also sound and complete, but has worst case complexity exponential in N.