NP-hardness of MAP in Ternary Tree Bayesian Networks

C. P. de Campos

Research output: Working paper


This paper strengthens the NP-hardness result for the (partial) maximum a posteriori (MAP) problem in Bayesian networks with topology of trees (every variable has at most one parent) and variable cardinality at most three. MAP is the problem of querying the most probable state configuration of some (not necessarily all) of the network variables given evidence. It is demonstrated that the problem remains hard even in such simplistic networks.
Original languageEnglish
Publication statusPublished - 2013

Bibliographical note

Tech Report No. IDSIA-06-13


Dive into the research topics of 'NP-hardness of MAP in Ternary Tree Bayesian Networks'. Together they form a unique fingerprint.

Cite this