Abstract

Abstract: In this talk, I will present the concept of submdodularity and relate it to certain optimisation problems, which can be described as Valued Constraint Satisfaction Problems. This framework is equivalent to other frameworks, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation or Markov Random Fields. It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. We answer the problem negatively. We relate our results to the problem of which submodular functions can be minimised using the Min-Cut/Max-Flow techniques.