Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99002 (February, 1999)

Optimal Augmenting a Submodular and Posi-modular Set Function by a Multigraph
by Hiroshi Nagamochi, Takashi Shiraki and Toshihide Ibaraki

Given a finite set $V$ and a set function $f:2^V\mapsto {\bf Z}$, we consider the problem of constructing an undirected multigraph $G=(V,E)$ such that the cut function of $G$ 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((T_f+1)n^4\log n)$ time, where $n=|V|$ and $T_f$ is the time to compute the value of $f(X)$ for a subset $X\subset V$.