Abstract: We consider the following constrained maximization problem in discrete probabilistic graphical models (PGMs). Given two (possibly identical) PGMs $M_1$ and $M_2$ defined over the same set of variables and a real number $q$, find an assignment of values to all variables such that the probability of the assignment is maximized w.r.t. $M_1$ and is smaller than $q$ w.r.t. $M_2$. We show that several explanation and robust estimation queries over graphical models are special cases of this problem. We propose a class of approximate algorithms for solving this problem. Our algorithms are based on a graph concept called $k$-separator and heuristic algorithms for multiple choice knapsack and subset-sum problems. Our experiments show that our algorithms are superior to the following approach: encode the problem as a mixed integer linear program (MILP) and solve the latter using a state-of-the-art MILP solver such as SCIP.