The Expressive Power of Binary Submodular Functions

Stanislav Zivny (joint work with David Cohen and Peter Jeavons)

 

Abstract:

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. Using a connection between the

expressive power of valued constraints and certain algebraic properties

of functions, we answer this question negatively.

Our results have several corollaries. First, we characterize precisely

which submodular functions of arity 4 can be expressed by binary sub-

modular functions. Next, we identify a novel class of submodular functions

of arbitrary arities which can be expressed by binary submodular functions,

and therefore minimised efficiently using a so-called expressibility reduction

to the Min-Cut problem. More importantly, our results imply limitations on this

kind of reduction and establish for the first time that it cannot be used in general

to minimise arbitrary submodular functions. Finally, we refute a conjecture

of Promislow and Young on the structure of the extreme rays of the cone of

Boolean submodular functions.