---
title: "New Complexity Results for MAP in Bayesian Networks"
authors:
  - "Cassio Polpo de Campos"
doi: "10.5591/978-1-57735-516-8/IJCAI11-351"
url: "https://ijcai.org/proceedings/2011/351"
pdf: "https://ijcai.org/proceedings/2011/0351.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2100-2105"
track: ""
keywords:
---

# New Complexity Results for MAP in Bayesian Networks

Cassio Polpo de Campos

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2100-2105. DOI: [10.5591/978-1-57735-516-8/IJCAI11-351](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-351)

## Abstract

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.