Polyhedral structure of submodular and posi-modular systems Original Research Article

Let V be a finite set, and R be the set of reals. A set function f : 2V→R is called intersecting submodular if f(X)+f(Y)⩾f(X∩Y)+f(Y∪X) for all intersecting X,Y⊂V, and intersecting posi-modular if f(X)+f(Y)⩾f(X−Y)+f(Y−X) for all intersecting X,Y⊂V, where X and Y intersecting if X∩Y≠∅, X−Y≠∅ and Y−X≠∅ hold. We consider the polyhedron P={z∈R−V | z(X)⩽f(X), ∀X ∈2V} for a system (V,f) with an intersecting submodular and posi-modular set function f : 2V→R, where R−V denotes the set of |V|-dimensional nonpositive vectors and z(X) for a z∈R−V and X⊆V is defined by ∑i∈Xz(i). We first prove that there is a laminar (i.e., nonintersecting) family X⊆2V−{∅,V} such that P is characterized by {z∈R−V | z(X)⩽f(X), ∀X∈X}. Based on this, we can solve in polynomial time the problem of augmenting edge-connectivity of a network so as to minimize the number of vertices having edges whose weights are increased.