# Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks

arXiv: https://arxiv.org/abs/1703.06045 · HTML: https://mlsanity.com/paper/1703.06045/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2017.

## Built on by (most cited first, 7 of 7)

- [Solving Marginal MAP Exactly by Probabilistic Circuit Transformations](https://mlsanity.com/paper/2111.04833/) (2021)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [Neural Network Approximators for Marginal MAP in Probabilistic Circuits](https://mlsanity.com/paper/2402.03621/) (2024)
- [Learning to Condition: A Neural Heuristic for Scalable MPE Inference](https://mlsanity.com/paper/2509.25217/) (2025)
- [Probably Approximately Correct Maximum A Posteriori Inference](https://mlsanity.com/paper/2601.16083/) (2026)
- [Learning to Guide Local Search for MPE Inference in Probabilistic Graphical Models](https://mlsanity.com/paper/2602.01475/) (2026)

## Abstract (arXiv)

We discuss the computational complexity of approximating maximum a posteriori inference in sum-product networks. We first show NP-hardness in trees of height two by a reduction from maximum independent set; this implies non-approximability within a sublinear factor. We show that this is a tight bound, as we can find an approximation within a linear factor in networks of height two. We then show that, in trees of height three, it is NP-hard to approximate the problem within a factor 2f(n) for any sublinear function f of the size of the input n. Again, this bound is tight, as we prove that the usual max-product algorithm finds (in any network) approximations within factor 2c · n for some constant c < 1. Last, we present a simple algorithm, and show that it provably produces solutions at least as good as, and potentially much better than, the max-product algorithm. We empirically analyze the proposed algorithm against max-product using synthetic and realistic networks.