Learning Bayesian Networks is NP-Complete - Chickering, Max (Learning from Data: Artificial Intelligence and Statistics V, 1996)
Algorithms for learning Bayesian networks from data have two components: a scoring metric and a search procedure. The scoring metric computes a score re ecting the goodness-of- t of the structure to the data. The search procedure tries to identify network structures with high scores. Heckerman et al. (1995) introduce a Bayesian metric, called the BDe metric, that computes the relative posterior probability of a network structure given data. In this paper, we show that the search problem of identifying a Bayesian network|among those where each node has at most K parents|that has a relative posterior probability greater than a given constant is NP-complete, when the BDe metric is used.