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.