ECAI-2002 Conference Paper

[full paper]

On the Complexity of the MPA Problem in Probabilistic Networks

Hans L. Bodlaender, Frank van den Eijkhof, Linda C. van der Gaag

The problem of finding the best explanation for a set of observations is studied within various disciplines of artificial intelligence. For a probabilistic network, finding the best explanation amounts to finding a value assignment to all the variables in the network that has highest posterior probability given the available observations. This problem is known as the MPA, or maximum probability assignment, problem. In this paper, we establish the computational complexity of the MPA problem and of various closely related problems. Among other results, we show that, while the MPA-p problem, where an assignment with probability at least p is to be found, is NP-hard, its fixed-parameter variant is solvable in linear time.

Keywords: Probabilistic Reasoning, Computational Complexity

Citation: Hans L. Bodlaender, Frank van den Eijkhof, Linda C. van der Gaag: On the Complexity of the MPA Problem in Probabilistic Networks. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.675-679.