As usual, we may encounter a problem of the following form: Given is an energy function $$$D_{c_i}(i)$$$ where $$$c_i \in [0 \dots k)$$$, and another energy function $$$V_{c_i,c_j}$$$ where $$$(i,j) \in E$$$. Minimize the total energy of the sum.

In certain conditions, such as: $$$k=2$$$ and $$$V_{0,0}+V_{1,1}\le V_{0,1}+V_{1,0}$$$, it can be solved by classic graph cut method.

More generally, what conditions are meet for $$$D$$$ and $$$V$$$ such taht it can be solved by graph cut. However, it's too difficult for me.