@techreport{Zivny08:sub-tr,
  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. <br/> 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&gt;=4, a subclass of k-ary submodular functions which are also expressible in this way. <br/> 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. <br/> 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.",
  address = "Oxford, UK",
  author = "Stanislav \v{Z}ivn\'y and Peter G. Jeavons",
  institution = "OUCL",
  month = "June",
  number = "RR-08-08",
  title = "Which submodular functions are expressible using binary submodular functions?",
  url = "http://zivny.cz/publications/zj08sub-tr.pdf",
  year = "2008",
}