This paper presents a characterization of energy functions that can be minimized using graph cuts in computer vision. The authors show that energy functions with binary variables can be minimized via graph cuts if they satisfy certain conditions. Specifically, for energy functions that can be written as a sum of functions of up to two variables, a necessary and sufficient condition is that each pairwise term satisfies a certain inequality. For energy functions that can be written as a sum of functions of up to three variables, the condition is that the entire function is "regular," meaning that all pairwise projections are regular. The authors also provide a general-purpose construction for minimizing such energy functions. The results are applicable to a wide range of vision problems, including stereo, motion, image restoration, and scene reconstruction. The paper also discusses the limitations of graph cuts and how they can be extended to handle more complex energy functions. The authors conclude that graph cuts provide a powerful and efficient method for minimizing certain types of energy functions in computer vision.This paper presents a characterization of energy functions that can be minimized using graph cuts in computer vision. The authors show that energy functions with binary variables can be minimized via graph cuts if they satisfy certain conditions. Specifically, for energy functions that can be written as a sum of functions of up to two variables, a necessary and sufficient condition is that each pairwise term satisfies a certain inequality. For energy functions that can be written as a sum of functions of up to three variables, the condition is that the entire function is "regular," meaning that all pairwise projections are regular. The authors also provide a general-purpose construction for minimizing such energy functions. The results are applicable to a wide range of vision problems, including stereo, motion, image restoration, and scene reconstruction. The paper also discusses the limitations of graph cuts and how they can be extended to handle more complex energy functions. The authors conclude that graph cuts provide a powerful and efficient method for minimizing certain types of energy functions in computer vision.