[edit]

# Almost No News on the Complexity of MAP in Bayesian Networks

*Proceedings of the 10th International Conference on Probabilistic Graphical Models*, PMLR 138:149-160, 2020.

#### Abstract

This article discusses the current state of the art in terms of
computational complexity for the problem of finding the most probable
configuration of a subset of variables in a multivariate domain
modelled by probabilistic graphical models such as Markov networks
(random fields) or Bayesian networks. It contains complexity proofs and an
algorithm for the problem and shows empirical results for Boolean
trees which may suggest tractability of the task in some special
cases.