Which submodular functions are expressible using binary submodular functions?
Stanislav Živný and Peter G. Jeavons
Abstract
Submodular functions occur in many combinatorial optimisation problems and a number of polynomial-time algorithms have been
devised to minimise such functions. The time complexity of the fastest known general algorithm for submodular function minimisation
(SFM) is O(n^6+n^5L), where n is the number of variables and L is the time required to evaluate the function.
However,
many important special cases of SFM can be solved much more efficiently, and with much simpler algorithms. For example, the
(s,t)-Min-Cut problem is a special case of SFM which can be solved in cubic time. Moreover, any submodular function which
can be expressed as a sum of binary submodular functions can be minimised by computing a minimal cut in a suitable graph.
It has been known for some time that all ternary submodular functions are expressible in this way, by introducing additional
variables. We have recently identified, for each k>=4, a subclass of k-ary submodular functions which are also expressible
in this way.
It was previously an open question whether all submodular functions could be expressed as a sum of binary
submodular functions over a larger set of variables: in this paper we show that they cannot. Moreover, we characterise precisely
which 4-ary submodular functions can be expressed in this way. This result can also be seen as characterising which pseudo-Boolean
functions of degree 4 can be expressed as projections of quadratic submodular functions.
Our results provide a more
efficient algorithm for certain discrete optimisation problems which can be formulated as valued constraint satisfaction problems
(VCSP). We define a new maximal class of VCSP instances with submodular constraints which are expressible using binary submodular
functions with a bounded number of additional variables. It follows that optimal solutions to such instances can be computed
in O((n+k)^3) time, where n is the number of variables and k is the number of higher-order (non-binary) constraints, by a
straightforward reduction to the (s,t)-Min-Cut problem.
Details
| Address |
Oxford‚ UK |
| Institution |
OUCL |
| Month |
June |
| Number |
RR−08−08 |
| Year |
2008 |
Links
Related pages
|
People |
|
|
Activities |