Energy minimization problems arise frequently when working with binary graph structures such as markov random fields (MRFs), commonly found in spatial statistics and image analysis. Connections between the energy minimization problem and network flow algorithms is well known and frequently used in optimizing these models. Under certain conditions -- namely, sub modularity â€“ these techniques, typically called graph cuts, allow for quickly finding the minimum energy state. We extend these known results in two ways; the first is with a fast approximation algorithm based on majorization for the case when the MRF is not sub modular. Second, we extend the graph cut results using theory from sub modular optimization. Our key result here, surprisingly, is a method for efficiently incorporating uncertainty information into the graph cuts, turning what is normally a binary cut into a collection of probabilistic level sets. We discuss the significance of this result in relation to image segmentation and detection/validation of boundary regions in spatial statistics. We conclude with several challenges and open questions.