Augmenting a submodular and posi-modular set function by a multigraph

Given a finite set V and a set function f : 2(V) bar right arrow Z, we cons ider the problem of constructing an undirected multigraph G = (V,E) such th at the cut function C-G: 2(V) bar right arrow Z of G and f together has val ue at least 2 for all non-empty and proper subsets of V. If f is intersecti ng submodular and posi-modular, and satisfies the tripartite inequality, th en we show that such a multigraph G with the minimum number of edges can be found in O((T-f + 1)n(4) log n) time, where n = |V| and T is the time to c ompute the value of f(X) for a subset X subset of V.