Finding a path is harder than finding a tree

Christopher Meek
Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, PMLR R3:192-195, 2001.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR3-meek01a, 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}, pages = {192--195}, year = {2001}, editor = {Richardson, Thomas S. and Jaakkola, Tommi S.}, volume = {R3}, series = {Proceedings of Machine Learning Research}, month = {04--07 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r3/meek01a/meek01a.pdf}, url = {https://proceedings.mlr.press/r3/meek01a.html}, 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.}, note = {Reissued by PMLR on 31 March 2021.} }
Endnote
%0 Conference Paper %T Finding a path is harder than finding a tree %A Christopher Meek %B Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2001 %E Thomas S. Richardson %E Tommi S. Jaakkola %F pmlr-vR3-meek01a %I PMLR %P 192--195 %U https://proceedings.mlr.press/r3/meek01a.html %V R3 %X 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. %Z Reissued by PMLR on 31 March 2021.
APA
Meek, C.. (2001). Finding a path is harder than finding a tree. Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R3:192-195 Available from https://proceedings.mlr.press/r3/meek01a.html. Reissued by PMLR on 31 March 2021.

Related Material