Deciding Morality of Graphs is NP-complete
classification
💻 cs.AI
keywords
decidinggraphnp-completeacyclicassociationscausalconcentrationcovariance
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.