# Deciding Morality of Graphs is NP-complete

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

## Key facts

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

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

- [Linear-Time Primitives for Algorithm Development in Graphical Causal Inference](https://mlsanity.com/paper/2506.15758/) (2025)

## Abstract (arXiv)

In order to find a causal explanation for data presented in the form of covariance and concentration matrices it is necessary to decide if the graph formed by such associations is a projection of a directed acyclic graph (dag). We show that the general problem of deciding whether such a dag exists is NP-complete.