劣モジュラ関数を最小化する奇数サイズ集合
1. はじめに
今回は，奇数サイズの部分集合の中で，劣モジュラ関数値が最小なものを求める方法を紹介します．劣モジュラ関数が多項式時間で最小化できることは広く知られていますが，実は劣モジュラ関数を最小化する奇数サイズ集合も，通常の劣モジュラ最小化を繰り返し行うことで求めることができます．
2. アルゴリズム
$S$を有限集合，$f:2^S\rightarrow \mathbf{R}$を劣モジュラ関数とします．ここで，$f$が劣モジュラであるとは，すべての部分集合$X,Y\subseteq S$に対して劣モジュラ不等式$f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)$が成り立つことをいいます．$f(X)$の値が最小となる奇数サイズの$X\subseteq S$を求めるアルゴリズム [1,2]*1*2を以下で説明します．紹介するアルゴリズムは，部分集合$T\subseteq S$に対して，$|X\cap T|$が奇数サイズとなる$X\subseteq S$の中で$f$を最小化するものを求めるという少し一般化された設定のものです*3*4．
まず，$|T|$が奇数のときは，以下のように$|T|$が偶数の場合に帰着します：各$t\in T$に対して，$S\setminus \{t\}$の部分集合であって$T\setminus \{t\}$との交叉が奇数サイズのもののうち$f$を最小化する集合を求め，それらについての$f$の値と$\min\{f(U)\mid U\supseteq T\}$を比べ，最小のものを出力すればokです．以下では$|T|$が偶数の場合を考えます．
まず，通常の劣モジュラ最小化アルゴリズムで，$X\cap T,T\setminus X\neq \emptyset$を満たす$X\subseteq S$（このような$X$を$T$を分割する集合とよぶことにします）のうち$f(X)$を最小化するものを求めます．これは，各$s,t\in T$に対して$s$を含み$t$を含まない集合の中で$f$を最小化するものを求めることで達成できます．$|X\cap T|$が奇数ならokです．$|X\cap T|$が偶数のときは，$Y\subseteq S$であって，$T\setminus X$を分割せず，かつ$|X\cap T\cap Y|$が奇数なものの中で$f$を最小化するものと，$Z\subseteq S$であって，$X\cap T$を分割せず，かつ$|(T\setminus X)\cap Z|$が奇数なものの中で$f$を最小化するものを求めます（これは，$T\setminus X$や$X\cap T$を縮約して一要素にし，$T$のサイズがより小さい場合のアルゴリズムを回すことで帰納的に求められます）．そして，$Y$と$Z$のうち$f$の値が小さいものを出力すると，実はそれが$T$との交叉が奇数サイズの集合の中で$f$の値を最小化するものになっています！以下でその証明をします．
矛盾を導くために，$|W\cap T|$が奇数の集合$W\subseteq S$の中で$f(W)$を最小化するものが，$f(W)<f(Y),f(Z)$を満たすと仮定します．$|W\cap X\cap T|$と$|W\cap (T\setminus X)|$のどちらか一方は奇数なので，$|W\cap X\cap T|$が奇数の場合を考えます（$|W\cap (T\setminus X)|$が奇数の場合も同じ流れで示せます）．すると$f(W)<f(Y)$と$Y$の最小性から，$W$は$T\setminus X$を分割することが分かります．つまり$W\cup X$は$T$を分割するので，$X$の最小性から$f(X)\leq f(W\cup X)$が成り立ちます．また，$|W\cap X\cap T|$は奇数なので，$W$の最小性から$f(W)\leq f(W\cap X)$が成り立ちます．これと劣モジュラ不等式$f(W)+f(X)\geq f(W\cup X)+f(W\cap X)$から，$f(W)=f(W\cap X)$が成り立ちます．$W\cap X$は$T\setminus X$を分割しないので，$Y$の最小性から$f(Y)\leq f(W\cap X)=f(W)$が成り立ちますが，これは仮定に矛盾します．
計算量については，$|T|$が偶数の場合は帰納法のステップが$O(|T|)$回あり，各ステップで劣モジュラ最小化問題を$O(|T|^2)$回解くことになるので，合計$O(|T|^3)$回劣モ最小化をする必要があります．
3. コメント
やや複雑ですが，なんだかパズル的で面白い話ですね．
また，この結果はparity family上の劣モジュラ関数最小化問題に拡張されています [3]．$\mathcal{F}\subseteq 2^S$がparity familyであるとは，すべての$X,Y\in 2^S\setminus \mathcal{F}$に対して，$X\cup Y,X\cap Y$が両方とも$\mathcal{F}$に属するか，両方とも属さないかのどちらかが成り立つことをいいます．parity familyは奇数サイズ集合の全体からなる族の一般化ですが，parity familyに属する集合の中で劣モジュラ関数値が最小のものを求める問題も，通常の劣モジュラ最小化を繰り返し行うことで多項式時間で解くことができます．
参考文献
[1] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169–197, 1981.
[2] M. Grötschel, L. Lovász, and A. Schrijver. Corrigendum to our paper ``The ellipsoid method and its consequences in combinatorial optimization''. Combinatorica, 4:291–295, 1984.
[3] M. X. Goemans and V. S. Ramakrishnan. Minimizing submodular functions over families of sets. Combinatorica, 15:499–513, 1995
