Optimization techniques based on graph cuts have become a standard tool for
many vision applications. These techniques allow to minimize efficiently certain energy
functions corresponding to pairwise Markov Random Fields (MRFs). Currently, there
is an accepted view within the computer vision community that graph cuts can only
be used for optimizing a limited class of MRF energies (e.g. submodular functions).
In this survey we review some results that show that graph cuts can be applied
to a much larger class of energy functions (in particular, non-submodular functions).
While these results are well-known in the optimization community, to our knowledge
they were not used in the context of computer vision and MRF optimization. We
demonstrate the relevance of these results to vision on the problem of binary texture
restoration.