Polyhedral structure of submodular and posi-modular systems

Let V be a finite set, and R be the set of reals. A set function f : 2(V) - -> R is called intersecting submodular if f(X) + f(Y) greater than or equal to f(X boolean AND Y) + f(Y boolean OR X) for all intersecting X, Y subset of V, and intersecting posi-modular if f(X) + f(Y)greater than or equal to f(X - Y) + f(Y - X) for all intersecting X, Y subset of V, where X and Y i ntersecting if X boolean AND Y not equal empty set, X - Y not equal empty s et and Y - X not equal empty set, hold. We consider the polyhedron P = {z i s an element of R--(V) /z(X)less than or equal tof(X), For AllX is an eleme nt of 2(V)} for a system (V, f) with an intersecting submodular and posi-mo dular set function f : 2(V) --> R, where R--(V) denotes the set of /V/-dime nsional nonpositive vectors and z(X) for a z is an element of R--(V) and X subset of or equal to V is defined by Sigma (i is an element ofX) z =(i). W e first prove that there is a laminar (i.e., nonintersecting) family R subs et of or equal to 2(V) - {empty set, V} such that P is characterized by (z is an element of R--(V) /z(X) less than or equal to f(X), For AllX is an el ement of 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 v ertices having edges whose weights are increased. (C) 2000 Elsevier Science B.V. All rights reserved.