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$.