The structure of optimal solutions to the submodular function minimization problem

Abstract

In this paper, we study the structure of optimal solutions to the submodular function minimization problem. We introduce prime sets and pseudo-prime sets as basic building block of minimizer sets, and investigate composition, decomposition, recognition, and certification of prime sets. We show how Schrijver's submodular function minimization algorithm can be modified to construct in polynomial time a prime or pseudoprime decomposition of the ground set V. We also show that the final vector x obtained by this algorithm is an extreme point of the polyhedron P:= { x <= 0 : x(A) <= f(A), for all subsets A of V }.