Deciding Morality of Graphs is NP-complete
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 6 Mar 2013.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2025: 1.
1 paper.