Hypergraphic submodular function minimization

We generalize the results of Anglès d'Auriac, Iglói, Preissmann and Sebő [1,6] concerning graphic submodular function minimization. They use a subroutine due to Padberg and Wolsey (1983) [5] that cannot be adapted to hypergraphs. Instead of their approach we consider fractional orientations and the push-relabel method Goldberg and Tarjan (1988) [4]. The complexity of the resulting algorithm in a hypergraph is O(n4+n3m), where n,m are the number of nodes and hyperedges, respectively.