Learning Sparse Causal Models is not NP-hard
This addresses the computational complexity of causal discovery for researchers, proving it is less hard than previously thought for sparse cases, though it is incremental as it builds on existing algorithms like FCI.
The paper demonstrates that learning sparse causal models is not NP-hard, showing that a sound and complete model can be obtained in worst-case order N^{2(k+2)} independence tests for graphs bounded by node degree k, even with latent variables and selection bias.
This paper shows that causal model discovery is not an NP-hard problem, in the sense that for sparse graphs bounded by node degree k the sound and complete causal model can be obtained in worst case order N^{2(k+2)} independence tests, even when latent variables and selection bias may be present. We present a modification of the well-known FCI algorithm that implements the method for an independence oracle, and suggest improvements for sample/real-world data versions. It does not contradict any known hardness results, and does not solve an NP-hard problem: it just proves that sparse causal discovery is perhaps more complicated, but not as hard as learning minimal Bayesian networks.