On the Robustness of Most Probable Explanations
  In Bayesian networks, a Most Probable Explanation (MPE) is a complete
variable instantiation with a highest probability given the current evidence.
In this paper, we discuss the problem of finding robustness conditions of the
MPE under single parameter changes. Specifically, we ask the question: How much
change in a single network parameter can we afford to apply while keeping the
MPE unchanged? We will describe a procedure, which is the first of its kind,
that computes this answer for each parameter in the Bayesian network variable
in time O(n exp(w)), where n is the number of network variables and w is its
treewidth.
