[edit]

# Finding a path is harder than finding a tree

*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.