Finding a Path is Harder than Finding a Tree

C. Meek

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…