  Finding the most likely (MAP) configuration of a Markov random field (MRF) is
NP-hard in general. A promising, recent technique is to reduce the problem to
finding a maximum weight stable set (MWSS) on a derived weighted graph, which
if perfect, allows inference in polynomial time. We derive new results for this
approach, including a general decomposition theorem for MRFs of any order and
number of labels, extensions of results for binary pairwise models with
submodular cost functions to higher order, and an exact characterization of
which binary pairwise MRFs can be efficiently solved with this method. This
defines the power of the approach on this class of models, improves our toolbox
and expands the range of tractable models.
