Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2007-006 (February 06, 2007)

A Simple Extreme Subsets Algorithm for Submodular and Posi-modular Set Functions
by Hiroshi Nagamochi

pdf File


Let $f$ be a set function on a finite set $V$. A pair $\{u,v\}\subseteq V$ is called {\em flat} in $f$ if $f(X)\geq \min_{x\in X}f(\{x\})$ holds for all subsets $X\subseteq V$ with $|X\cap \{u,v\}|=1$. A subset $X\subseteq V$ is called an extreme subset of $f$ if $f(Y)>f(X)$ holds for all nonempty and proper subsets $Y$ of $X$. In this paper, we first define a minimum degree ordering (MD ordering) of $V$, and show that the last two elements in an MD ordering give a flat pair of $f$ if $f$ is symmetric and crossing submodular. Based on this, we then give a simple $O(|V|^3)$-oracle time algorithm for computing all extreme subsets of a set function $g$ if $g$ is symmetric and crossing submodular or intersecting submodular and posi-modular.