In this paper we address the problem of finding the most
probable state of discrete Markov random field (MRF) with
associative pairwise terms. Although of practical importance,
this problem is known to be NP-hard in general.
We propose a new type of MRF decomposition, submodular
decomposition (SMD). Unlike existing decomposition
approaches SMD decomposes the initial problem into subproblems
corresponding to a specific class label while preserving
the graph structure of each subproblem. Such decomposition
enables us to take into account several types of
global constraints in an efficient manner. We study theoretical
properties of the proposed approach and demonstrate
its applicability on a number of problems.