Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function \(f:2^V \mapsto Z\), we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function \(C_G :2^V \mapsto Z{\text{ of }}G{\text{ and }}f\) together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in \(O\left( {\left( {T_f + 1} \right)n^4 \log n} \right)\) time, where \(n = \left| V \right|{\text{ and }}T_f\) is the time to compute the value of f(X) for a subset \(X \subset V\).