Finding a path is harder than finding a tree. (English) Zbl 0994.68120

Meek, C.

J. Artif. Intell. Res. (JAIR) 15, 383-389 (2001).

Summary: 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 an 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.

MSC:

68T05	Learning and adaptive systems in artificial intelligence
68R10	Graph theory (including graph drawing) in computer science

Keywords:

optimal path graphical model