*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.