Finding Submodularity Hidden in Symmetric Difference

A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y)$foranypair$X, Y \subseteq V$. The symmetric difference transformation (SD-transformation) of $f$ by a canonical set $S \subseteq V$isasetfunction$g$givenby$g(X) = f(X \vartriangle S)$for$X \subseteq V$,where$X \vartriangle S = (X \setminus S) \cup (S \setminus X)$denotesthesymmetricdifferencebetween$X$and$S$. Submodularity and SD-transformations are regarded as the counterparts of convexity and affine transformations in a discrete space, respectively. However, submodularity is not preserved under SD-transformations, in contrast to the fact that convexity is invariant under affine transformations. This paper presents a characterization of SD-stransformations preserving submodularity. Then, we are concerned with the problem of discovering a canonical set $S$, given the SD-transformation $g$ of a submodular function $f$ by $S$, provided that $g(X)$ is given by a function value oracle. A submodular function $f$ on $V$ is said to be strict if $f(X)+f(Y)>f(X\cup Y)+f(X\cap Y)$ holds whenever both $X\setminus Y$ and $Y\setminus X$ are nonempty. We show that the problem is solved by using $\mathrm{O}(\mathrm{\mid }V\mathrm{\mid })$ oracle calls when $f$ is strictly submodular, although it requires exponentially many oracle calls in general.