New Complexity Results for MAP in Bayesian Networks

C. P. de Campos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Citations (Scopus)


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. 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, a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable is developed. Approximation schemes were thought to be impossible, but here it is shown otherwise under the assumptions just mentioned, which are adopted in most applications.
Original languageEnglish
Title of host publicationInternational Joint Conference on Artificial Intelligence (IJCAI)
PublisherAAAI Press
Number of pages7
Publication statusPublished - 2011

Bibliographical note

(top 17%, oral presentation, double-blind peer reviewed by >3 reviewers)


Dive into the research topics of 'New Complexity Results for MAP in Bayesian Networks'. Together they form a unique fingerprint.

Cite this