  In the 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.
