ML Anthology

Finding a Path Is Harder than Finding a Tree

Christopher Meek
JAIR 2001 pp. 383-389
doi:10.1613/JAIR.914 /jair/2001/meek2001jair-finding/

Abstract

I consider the problem of learning an optimal path graphical model from data and show the problem to be NP-hard for the maximum likelihood and minimum description length approaches and a Bayesian approach. 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 JAIR Semantic Scholar

Cite

Text

Meek. "Finding a Path Is Harder than Finding a Tree." Journal of Artificial Intelligence Research, 2001. doi:10.1613/JAIR.914

Markdown

[Meek. "Finding a Path Is Harder than Finding a Tree." Journal of Artificial Intelligence Research, 2001.](https://mlanthology.org/jair/2001/meek2001jair-finding/) doi:10.1613/JAIR.914

BibTeX

@article{meek2001jair-finding,
  title     = {{Finding a Path Is Harder than Finding a Tree}},
  author    = {Meek, Christopher},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2001},
  pages     = {383-389},
  doi       = {10.1613/JAIR.914},
  volume    = {15},
  url       = {https://mlanthology.org/jair/2001/meek2001jair-finding/}
}