New Complexity Results for MAP in Bayesian Networks
Cassio de Campos
This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure), which extends previous complexity results. Furthermore, it is proven the existence of a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable. Approximation schemes were thought to be impossible for this problem, but we show otherwise under the assumptions just mentioned, which are widely adopted in most applications.