Reference Request: Submodular Minimization and Monotone Boolean Functions
As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean functions.  However, if the domain is non-Boolean, then binary submodular functions are not enough to express all submodular functions, even if hidden variables may be introduced.  (Apologies if I have missed a subtlety in your precise problem phrasing.)

The state of the art is discussed in this nice paper which has lots of links to related work, and that also makes the links to computer vision quite explicit:


Stanislav Živný, David A. Cohen, Peter G. Jeavons, The expressive power of binary submodular functions, DAM 157 3347–3358, 2009.  doi: 10.1016/j.dam.2009.07.001 (preprint)


In case your next question is about approximation, this recent paper looks at the approximation version:


Dorit S. Hochbaum, Submodular problems - approximations and algorithms, arXiv: 1010.1945


Edit: fixed link.