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.
Introduction
In the field of probabilistic reasoning, Bayesian Networks (BNs) serve as the gold standard for representing complex dependencies. However, a significant computational hurdle exists: the Maximum A Posteriori (MAP) problem. While standard belief updating is well-understood, MAP queries—which seek the most likely configuration of multiple variables simultaneously—are notoriously difficult, classified as $NP^{PP}$-complete in general. This research by Cassio P. de Campos provides a definitive map of these complexity limits and introduces a theoretical breakthrough for approximation.
Hardness in Simple Topologies
A primary contribution of this work is the proof that MAP remains NP-hard even in extremely simple network structures. Previous research had established hardness in polytrees, but often relied on variables having an astronomical number of states. This paper demonstrates that hardness persists in "real-world" simple scenarios.
Simple Trees and Naive Bayes
The author proves that MAP is NP-hard for simple tree structures, including the ubiquitous Naive Bayes model, when the number of states per variable is not strictly bounded. This finding challenges the assumption that structural simplicity alone guarantees computational tractability.
Polytrees and Sequence Models
The research further demonstrates that Decision-MAP is NP-hard even in binary polytrees (where treewidth $w=2$ and states $z=2$). This result extends to sequence models such as Hidden Markov Models (HMMs), which are represented by chain-like structures. Even with minimal interconnectedness, the state-space complexity can make finding the most likely scenario intractable.
The FPTAS Breakthrough
Despite the established hardness, the paper introduces the first Fully Polynomial Time Approximation Scheme (FPTAS) for MAP. This proves that if a network has limited "width" (treewidth) and a bounded number of states per variable—conditions common in many practical applications—a near-perfect solution is computationally reachable.
The core innovation is a lattice-based pruning technique. Instead of tracking every possible probability value, which grows exponentially, the algorithm discretizes the probability space into grid cells (hypercubes) and maintains only one representative potential per cell. This keeps the number of candidates polynomial while guaranteeing that the final error remains within a user-defined limit ($\epsilon$). Specifically, the algorithm provides a $(1+\epsilon)$ approximation in $O\left( \text{poly}(S(\mathcal{N}), 1/\epsilon) \right)$ time.
Conclusion
This research provides a definitive map of MAP complexity, showing that simplicity in topology is no shield against NP-hardness. However, by identifying the critical constraints of treewidth and state-cardinality, it offers a robust theoretical framework for efficient approximation, effectively solving a long-standing theoretical search for practical MAP solvers under common constraints.
Summary updated