  Markov random fields (MRFs) are a powerful tool for modelling statistical
dependencies for a set of random variables using a graphical representation. An
important computational problem related to MRFs, called maximum a posteriori
(MAP) inference, is finding a joint variable assignment with the maximal
probability. It is well known that the two popular optimisation techniques for
this task, linear programming (LP) relaxation and dual decomposition (DD), have
a strong connection both providing an optimal solution to the MAP problem when
a corresponding LP relaxation is tight. However, less is known about their
relationship in the opposite and more realistic case. In this paper, we explain
how the fully integral assignments obtained via DD partially agree with the
optimal fractional assignments via LP relaxation when the latter is not tight.
In particular, for binary pairwise MRFs the corresponding result suggests that
both methods share the partial optimality property of their solutions.
