マトロイドに対する貪欲法でないアルゴリズム

今回は，マトロイドの最大重み基を求める貪欲法でないアルゴリズムを紹介します*1．

マトロイドの最大重み基は，重みの大きな要素から選んでいく貪欲法によって求められます．この事実は多分有名だと思いますが，ではそれ以外の方法でマトロイドの最大重み基を求めることはできるのでしょうか？

実は，貪欲法よりももう少しテキトーな順番で要素を選んでいっても，最大重み基を求めることができます．今回はその方法を紹介します*2．

1. 定義など

マトロイドの用語の定義をします．知っている方は飛ばしてもらって大丈夫です．

 $E$を有限集合とする．$\mathcal{I}\subseteq 2^E$に対して，$M:=(E,\mathcal{I})$がマトロイドであるとは，次の三つの条件を満たすことをいう．

1. $\emptyset \in \mathcal{I}$,
2. $X\subseteq Y\in \mathcal{I}\Rightarrow X\in \mathcal{I}$,
3. $X,Y\in \mathcal{I},\ |X|<|Y|\Rightarrow \exists e\in Y\setminus X\ $s.t. $X+e\in \mathcal{I}$.

$E$を$M $の台集合とよび，$\mathcal{I}$に属する集合を独立集合とよぶ．$\mathcal{I}$を独立集合族とよぶ．また，極大な独立集合を基とよび，基をすべて集めてできる集合族を基族とよぶ．マトロイドのすべての基のサイズは等しいことが知られている．

マトロイド$M=(E,\mathcal{I})$の基族を$\mathcal{B}$とおく．$M $の双対マトロイド$M^*$とは，台集合が$E$であり，次のように定義される基族$\mathcal{B}^*$をもつマトロイドである．

$$\mathcal{B}^*:=\{B\subseteq E\mid E\setminus B\in \mathcal{B}\}.$$

 つまり，$\mathcal{B}^*$は$\mathcal{B}$に属する基の補集合を集めた集合族である． $M^*$の独立集合族は$\mathcal{B}^*$に属する基の部分集合たちからなる族，つまり$\mathcal{I}^*:=\{X\subseteq E\mid \exists B\in \mathcal{B}^* \mathrm{s.t.} X\subseteq B\}$である．

マトロイド$M=(E,\mathcal{I})$に対して，独立集合でない集合$X\notin \mathcal{I}$を従属集合とよぶ．極小な従属集合をサーキットとよぶ．また，双対マトロイド$M^*$のサーキットをコサーキットとよぶ．

2. 問題設定とアルゴリズム

以下のマトロイドの最大重み基問題を考えます．

マトロイドの最大重み基問題

入力: マトロイド$M=(E,\mathcal{I})$*3，重み関数$w:E\rightarrow \mathbf{R}$

タスク: $\sum_{b\in B} w(b)$が最大の基$B $を求める．

 この問題に対するアルゴリズムとして，空集合$F:=\emptyset $から始めて，重みの大きい順に要素を選んでいき，その要素を$F $に加えても独立集合のままなら順次$F$に加えていく，という貪欲アルゴリズムは有名だと思います．実は，このアルゴリズムよりも少しテキトーな順番で要素を選んでいく次のようなアルゴリズムでも，きちんと最大重み基を求めることができます．

アルゴリズム

• $F:=\emptyset$.
• $M $のコサーキットであって，$F$と交わらないもの$C^*\subseteq E\setminus F$があれば，どれでも良いので一つ選ぶ．この$C^*$に含まれる要素の中で最大重みのものを$F$に加える．これを繰り返す．
• そのようなコサーキットがなければ，$F$を出力する．実はこの$F$が最大重みの基になっている．

このアルゴリズムは，$M $の任意の基$B$がコサーキット$C^*$と必ず交わるので，とりあえず$C^*$に含まれる要素の中で最大重みのものを基の要素として採用していく，ということをしています．これもある意味貪欲法と呼べるかもしれません．重みが大きい順に要素を選んでいく貪欲法も上のアルゴリズムの特殊ケースとして見ることができて，$E\setminus F$における最大重みの要素を含むコサーキットが（あれば）常に選ばれる場合に対応します*4．

それではこのアルゴリズムの正当性を示していきます．

アルゴリズムの正当性

次の二つを順に示す．

1. $F$が常に$M $の独立集合であること
2. 最終的に出力される$F$が$M $の最大重み基であること

1.の証明

 まず重要な補題を一つ示す:

補題

マトロイド$M $の任意のサーキット$C$とコサーキット$C^*$に対して，$\left|C\cap C^*\right|\neq 1.$

証明

$C\cap C^*=\{e\}$と仮定する．すると，$C-e,\ C^*-e$はそれぞれ$M,\ M^*$の独立集合である．さらに，仮定から$C-e,\ C^*-e$は交叉しない．$C^*-e$は$M^*$の独立集合なので，$C^*-e$を含む$M^*$の基が存在し，その補集合は$C^*-e$を含まない$M $の基である（$B$とおく）．$B$と$C-e$に対して，マトロイドの定義の条件3を繰り返し用いることで，$C-e$を含み，$C^*-e$を含まない$M $の基$B'$が得られる．すると$E\setminus B'$は$M^*$の基であり，$C^*-e$を含む．$B'$と$E\setminus B'$のどちらかは$e$を含むが，これは両者の独立性に矛盾． $\Box$

1.の証明に入る．アルゴリズムの始めの時点では，$F$は空集合なので独立集合である．アルゴリズムのある段階で，コサーキット$C^*\subseteq E\setminus F$の最大重みの要素$e$が選ばれ，$F\in \mathcal{I}$かつ$F+e\notin \mathcal{I}$であったとする．このとき，$F+e$は従属集合なので，$e$を含むサーキット$C\subseteq F+e$が存在する．ここで，コサーキット$C^*$とサーキット$C$は$e$を含むので，補題から$\left|C\cap C^*\right|\geq 2$がわかる．しかし，$C^*\subseteq E\setminus F,\ C\subseteq F+e$なので，$\left|C\cap C^*\right|\leq 1$であり矛盾． $\Box$

2.の証明

まず，最終的に出力される$F$が$M $の基であることを示す．$E\setminus F$に包含されるコサーキットが存在しない場合，$E\setminus F$は$M^*$の独立集合である．さらに，1.から，最終的に出力される$F$は$M $の独立集合なので，この$F$は$M $の基である．

次に，アルゴリズムのどの段階でも，$F$を包含する$M $の最大重み基が存在することを示す．これを示せば，最終的に出力される$F$が$M $の最大重み基であることがわかる．アルゴリズムの始めの時点では，$F$は空集合なので$F$を包含する最大重み基は存在する．アルゴリズムのある段階で，$F$を包含する最大重み基が存在し，次に$F$に加える要素としてコサーキット$C^*\subseteq E\setminus F$の最大重みの要素$e$が選ばれたとする．$F$を包含する最大重み基を$B$とおく．$B+e$の部分集合であるサーキット$C\subseteq B+e$に対して，$C$は$e$を含むので，補題から$\left|C\cap C^*\right|\geq 2$がわかる．$e$と異なる$e'\in C\cap C^*$をとると，$e$の選び方から$w(e')\leq w(e)$が成り立つ．ここで，$B+e-e'$は，$M $の基であり*5，重みは$B$の重み以上である．さらに，$F+e\subseteq B+e-e'$なので，$B+e-e'$は$F+e$を包含する$M $の最大重み基である． $\Box$

これでアルゴリズムの正当性を示すことができました．

 余談

最小全域木問題は，マトロイドの最大（小）重み基を求める問題の特殊ケースとして見ることができます．最小全域木問題には，マトロイドの貪欲法に対応するKruskal法と呼ばれるアルゴリズムが知られています．一方で，Primのアルゴリズムと呼ばれる，連結性を保つという条件のもと最小重みの辺を順次加えていくアルゴリズムでも最小全域木問題を解くことができます．では，マトロイドに対してもPrimのアルゴリズムに対応するものは考えられるのでしょうか？

実は，2章で紹介したアルゴリズムは，Primのアルゴリズムも特殊ケースとして（ある意味）含んでいます．つまり，Primのアルゴリズムは，すでに選ばれた辺によって連結になっているグラフの頂点たちと，それ以外の頂点をカットする辺の集合の中から，最も重みの小さな辺を選んでいくアルゴリズムです．グラフ的マトロイドのコサーキットは元のグラフの極小カットなので，Primのアルゴリズムは，カットの中で最小重みの辺を含む（カットの部分集合である）極小カットが常にコサーキットとして選ばれる場合の2章のアルゴリズム，と理解することができます（ちょっと強引かもしれませんが）．

*1:ブログ名が「blogoid」でありながら，実はマトロイドの記事を書くのは初めてです．

*2:元ネタは，コルテフィーゲンの「組合せ最適化」の演習問題（6章の問題8）で，今回はそれのマトロイド版です．

*3:細かいことを言うと独立性オラクル（$X\in \mathcal{I}$かどうかを定数時間で判定してくれるオラクル）で与えられる設定を考えます．

*4:$M $の独立集合$F\in \mathcal{I}$と要素$e\in E\setminus F$に対して，$F+e\in \mathcal{I}$であることと，$e$を含む$M $のコサーキット$C^*\subseteq E\setminus F$が存在することは同値なので．

*5:マトロイドの独立集合$I$に要素$e$を加えて従属集合になったとき，$I+e$が部分集合として持つサーキットは唯一つという性質を暗に用いています．