Department of Applied Mathematics & Physics, Kyoto Univiversity
Technical Report #97009 (November, 1997)
A Note on Minimizing Submodular Functions
by Hiroshi Nagamochi and Toshihide Ibaraki
For a given submodular function $f$
on a finite set $V$, we consider the problem of finding a nonempty
and proper subset $X$ of $V$ that minimizes $f(X)$.
If the function $f$ is symmetric, then the problem
can be solved by a purely combinatorial algorithm
due to Queyranne (1995).
This note considers a slightly more general condition than
symmetry, i.e.,
$f(X)+f(Y)\geq f(X-Y)+f(Y-X)$ for all $X,Y\subseteq V$,
and shows that a modification of Queyranne's algorithm solves
the problem by using $O(|V|^3)$ calls to function value oracle.