  The maximum a posteriori (MAP) configuration of binary variable models with
submodular graph-structured energy functions can be found efficiently and
exactly by graph cuts. Max-product belief propagation (MP) has been shown to be
suboptimal on this class of energy functions by a canonical counterexample
where MP converges to a suboptimal fixed point (Kulesza & Pereira, 2008).
  In this work, we show that under a particular scheduling and damping scheme,
MP is equivalent to graph cuts, and thus optimal. We explain the apparent
contradiction by showing that with proper scheduling and damping, MP always
converges to an optimal fixed point. Thus, the canonical counterexample only
shows the suboptimality of MP with a particular suboptimal choice of schedule
and damping. With proper choices, MP is optimal.
