# On MAP Inference by MWSS on Perfect Graphs

arXiv: https://arxiv.org/abs/1309.6872 · HTML: https://mlsanity.com/paper/1309.6872/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2013.

## Built on by (most cited first, 1 of 1)

- [pRSL: Interpretable Multi-label Stacking by Learning Probabilistic Rules](https://mlsanity.com/paper/2105.13850/) (2021)

## Abstract (arXiv)

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.