Finding a Path is Harder than Finding a Tree

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.

Cited by in corpus (7)

• Large-Sample Learning of Bayesian Networks is NP-Hard
• Finding Optimal Bayesian Networks
• Parameterized Complexity Results for Exact Bayesian Network Structure Learning
• Graphical modeling of stochastic processes driven by correlated errors
• Learning Factor Graphs in Polynomial Time & Sample Complexity
• Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu