ML Anthology

Finding a Path Is Harder than Finding a Tree

Christopher Meek
AISTATS 2001 pp. 192-195
/aistats/2001/meek2001aistats-finding/

Abstract

This note shows that the problem of learning an optimal chain graphical model from data is NP-hard for the Bayesian, maximum likelihood, and minimum description length approaches. This hardness result holds despite the fact that the problem is a restriction of the polynomially solvable problem of finding the optimal tree graphical model.

PDF AISTATS Semantic Scholar

Cite

Text

Meek. "Finding a Path Is Harder than Finding a Tree." Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001.

Markdown

[Meek. "Finding a Path Is Harder than Finding a Tree." Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001.](https://mlanthology.org/aistats/2001/meek2001aistats-finding/)

BibTeX

@inproceedings{meek2001aistats-finding,
  title     = {{Finding a Path Is Harder than Finding a Tree}},
  author    = {Meek, Christopher},
  booktitle = {Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics},
  year      = {2001},
  pages     = {192-195},
  volume    = {R3},
  url       = {https://mlanthology.org/aistats/2001/meek2001aistats-finding/}
}