Approximating MAPs for belief networks is NP-hard and other theorems

Finding maximum a posteriori (MAP) assignments, also called Most Probable Explanations, is an important problem on Bayesian belief networks. Shimony has shown that finding MAPs is NP-hard. In this paper, we show that approximating MAPs with a constant ratio bound is also NP-hard. In addition, we examine the complexity of two related problems which have been mentioned in the literature. We show that given the MAP for a belief network and evidence set, or the family of MAPs if the optimal is not unique, it remains NP-hard to find, or approximate, alternative next-best explanations. Furthermore, we show that given the MAP, or MAPs, for a belief network and an initial evidence set, it is also NP-hard to find, or approximate, the MAP assignment for the same belief network with a modified evidence set that differs from the initial set by the addition or removal of even a single node assignment. Finally, we show that our main result applies to networks with constrained in-degree and out-degree, applies to randomized approximation, and even still applies if the ratio bound, instead of being constant, is allowed to be a polynomial function of various aspects of the network topology. (C) 1998 Elsevier Science B.V. All rights reserved.