ML Anthology

Deciding Morality of Graphs Is NP-Complete

Thomas Verma, Judea Pearl
UAI 1993 pp. 391-399
doi:10.1016/B978-1-4832-1451-1.50052-4 /uai/1993/verma1993uai-deciding/

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.

PDF UAI Semantic Scholar

Cite

Text

Verma and Pearl. "Deciding Morality of Graphs Is NP-Complete." Conference on Uncertainty in Artificial Intelligence, 1993. doi:10.1016/B978-1-4832-1451-1.50052-4

Markdown

[Verma and Pearl. "Deciding Morality of Graphs Is NP-Complete." Conference on Uncertainty in Artificial Intelligence, 1993.](https://mlanthology.org/uai/1993/verma1993uai-deciding/) doi:10.1016/B978-1-4832-1451-1.50052-4

BibTeX

@inproceedings{verma1993uai-deciding,
  title     = {{Deciding Morality of Graphs Is NP-Complete}},
  author    = {Verma, Thomas and Pearl, Judea},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year      = {1993},
  pages     = {391-399},
  doi       = {10.1016/B978-1-4832-1451-1.50052-4},
  url       = {https://mlanthology.org/uai/1993/verma1993uai-deciding/}
}