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.