J. Kwisthout. Two new notions of abduction in Bayesian networks. Technical report: ICIS-R10005, November, Radboud University Nijmegen, 2010.

Most Probable Explanation and (Partial) MAP are well-known problems in Bayesian networks that correspond to Bayesian or probabilistic inference of the most probable explanation of observed phenomena, given full or partial evidence. These problems have been studied extensively, both from a knowledge-engineering starting point (see [15] for an overview) as well as a complexity-theoretic point of view (see [13] for an overview). Algorithms, both exact and approximate, are studied in e.g. [21, 25, 19, 28]. In this paper, we introduce two new notions of abduction-like problems in Bayesian networks, motivated from cognitive science, namely the problem of finding the most simple and the most informative explanation for a set of variables, given evidence. We define
and motivate these problems, show that these problems are computationally intractable in general, but become tractable when some particular constraints are met.

J. Kwisthout. Most Probable Explanations in Bayesian Networks: complexity and tractability. Technical report: ICIS-R10001, March, Radboud University Nijmegen, 2010.

An overview is given of definitions and complexity results of a number of variants of the problem of probabilistic inference to the most probable explanation of a set of hypotheses given observed phenomana.