A set function f on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any two subsets S \subseteq T \subseteq E and an element x outside T, we have f(T + x) - f(T) \leq f(S+x) - f(S).
Submodular minimization problem asks for finding the minimum value a given submodular function takes. There are many combinatorial optimization problems that reduce to submodular minimization, for example, bipartite matching, max flow min cut, arborescences, disjoint spanning trees etc. All these problems admit algebraic algorithms, i.e., algorithms involving matrix rank computations. One can ask what is the most general class of submodular functions whose minimization admits an algebraic algorithm. Towards this, we define the class of 'linearly representable submodular functions (LRSF)', which is based on the rank functions of families of subspaces and captures all the above combinatorial examples. We give an algebraic algorithm for minimizing LRSF.
Our algebraic algorithm for this class of functions can be parallelized, and thus, puts the problem of finding the minimizing set in the complexity class randomized NC. Further, we derandomize our algorithm so that it needs only poly-logarithmic random bits. We also identify combinatorial problems which are captured by LRSF minimization, but any explicit algebraic algorithms were not given before.
