Deciding Morality of Graphs is NP-complete
This result is significant for researchers in causal inference and graph theory, as it establishes computational hardness for a foundational problem, though it is incremental in the sense that it builds on known complexity theory.
The paper tackled the problem of determining if a graph derived from covariance and concentration matrices can be projected from a directed acyclic graph (dag), proving that this general decision problem is NP-complete.
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.