マトロイド

マトロイド(matroid)はある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって最適解が得られることは非常に重要である。

定義

E={1,2,3}におけるそれぞれの例。左は(A1),(A2),(A3)を満たすからマトロイド。中央は(A1),(A2)を満たすから独立性システム。右は(A1),(A3)を満たすからグリードイド。

有限集合Eと部分集合F⊆2^Eとする(E,F)について

• (A1)$\emptyset\in{F}$
• (A2)X⊆Y∈FならばX∈F
• (A3)X,Y∈F,|X|>|Y|ならば$Y\cup\{x\}\in{F}$となる$x{\in}X\setminus{Y}$が存在する。

(A1),(A2),(A3)を満たすとき、マトロイドと呼ばれ、(A1)及び(A2)のみを満たすとき独立性システム(independence system)と呼ばれる。さらに(A1)及び(A3)を満たすときグリードイド(greedoid)と呼ばれる。

以下に本項で使う用語の定義を挙げる。

• 独立(independent) - Fの要素
• 従属(dependent) - $2^E\setminus{F}$の要素
• サーキット(circuit) - 極小な従属集合
• 基(basis) - 極大な独立集合
• Xの基 - X⊆EとするXの部分集合の中で極大な独立集合

Xを赤い辺、Yを青い辺とする。それぞれは明らかにハミルトン閉路の部分集合である。$|X|=8>6=|Y|$だが、赤い辺のいずれを青い辺に加えても、枝分かれしてしまうのでハミルトン閉路の部分集合にはなり得ない。よって、「Fはハミルトン閉路の部分集合」という条件では(A3)を満たさない。

マトロイド及び独立性システムの定義を与えたが、ひどく抽象的で理解しづらいかもしれない。ここでは具体的なモデルとしてグラフで考えよう。Eを辺の集合とする。Fは辺の任意の組合せの中で(A2)の条件を満たすものでなくてはならない。そのために「Fは森集合」や「Fはハミルトン閉路の部分集合」という条件を与える。これらはいずれも(A2)を満たす。なぜならば、森から辺を取り去っても森であるし、ハミルトン閉路の部分集合から辺を取り去ってもハミルトン閉路の部分集合だからである。しかし「Fはハミルトン閉路の部分集合」という条件では図に示すように(A3)を満たさない。対して「Fは森集合」は(A3)を満たすから、Eをグラフの辺集合、Fを森集合とする組(E,F)はマトロイドであるということが言える。

Fを森集合とした場合、従属集合は閉路を持つグラフの集合であるから、サーキットとは単純閉路となっている辺集合である。また(Xの)基とは(Xの部分集合の中で)できうる最大の森のことで、明らかに(Xでカバーされる)点の数-1本の辺で作られる森が最大であり、この森の集合を言う。

Eをグラフの辺集合、Fを森集合とする(E,F)はマトロイドになることは上述したが、それも含めて次のような場合もマトロイドになって特別に名前が与えられている。

ベクトルマトロイド(vector matroid)

Eは体上の行列Cの列集合で、Fの元に含まれる列集合はその体上で線形独立である。

体を理解しなくても、その部分を実数と読み替えれば線形代数でよく知られた事実よりマトロイドであることが分かる。本項ではベクトルマトロイドと捉えて解説することはないが、マトロイドという名前が行列(matrix)によるという事実を見ても分かるとおり、歴史上は行列の線形独立性から発展した概念である。行列からの導入は[1]に詳しい。

閉路マトロイド(cycle matroid)

Eは無向グラフGの辺集合であり、Fは閉路のない辺集合(森)の族。しばしばグラフGが閉路マトロイドであることをM(G)と書く。

グラフ的マトロイド(graphic matroid)

(E,F)はマトロイドであり、閉路マトロイドと同型であるときグラフ的マトロイドと呼ぶ。つまり、EとFの定義はどうであれ(たとえグラフと関係なさそうに見えても)、閉路マトロイドと同一視できるものを言う。例えば、E={1,2,3},F={f⊆E²,|f|≦2}は3つの辺を持つグラフの閉路マトロイドと同一視できるからグラフ的マトロイドであると言える。なお、これは次に紹介する一様マトロイドの例でもある。

一様マトロイド(uniform matroid)

Eは有限集合とし、ある整数k以下の元数を持つ2^Eの部分集合。明らかに基は元数がkであるようなEの部分集合である。

ランク

ランク(rank)関数は独立性システム(E,F)についてX⊆Eに対してr(X)=max{|Y|:Y⊆X,Y∈F}と定義できる。グラフで考えればFが森集合ならば、Xから作れる最大の森の辺数であるから、カバーしている点の個数に依存するので|Y|はどんなY⊆X,Y∈Fについても一定である。この事実は(A3)からも明らかであり、一般にマトロイドの場合はEの部分集合Xに対してXのどの基も元数は等しい。つまり、マトロイドならばランク関数をr(X)={|Y|:Y⊆X,Y∈F}としても構わない。

独立性システム(E,F)のランク関数rは任意のX,Y⊆Eとx,y∈Eについて次の性質を持つ。

• (R1)r(X)≦|X|
• (R2)X⊆Yならばr(X)≦r(Y)である。
• (R3)$r(\emptyset)=0$

さらに、マトロイド(E,F)ならば次の性質も持つ。

• (R4)r(X∪Y)+r(X∩Y)≦r(X)+r(Y)
• (R5)r(X)≦r(X∪{x})≦r(X)+1
• (R6)r(X∪{x})=r(X∪{y})=r(X)ならばr(X∪{x,y})=r(X)

特に(R4)に示されているようにランク関数が劣モジュラーであることはマトロイドの極めて重要な性質である。

いくつかの例を挙げよう。前述した通り閉路マトロイドにおいてXの基の元数はXがカバーする点の数より1小さいからr(X)=(Xがカバーする点数)-1と書ける。また、E={1,2,3},F={{1},{2},{1,2}}というマトロイドならばr({1})=1,r({1,2})=2,r({1,2,3})=2,r({1,3})=1等となる。

閉包

閉包(closure)関数は独立性システム(E,F)についてX⊆Eに対してσ(X)={y∈E:r(X∪{y})=r(X)}と定義でき、σ(X)をXの閉包と呼ぶ。

マトロイド(E,F)の閉包関数σは任意のX,Y⊆Eとx,y∈Eについて次の性質を持つ。

• (L1)X⊆σ(X)
• (L2)X⊆Yならばσ(X)⊆σ(Y)
• (L3)σ(X)=σ(σ(X))
• (L4)$y\not\in\sigma(X),y\in\sigma(X\cup\{x\})$ならばx∈σ(X∪{y})

ランク商

下方ランク関数ρをXに含まれる基の最小元数とする。つまり、ρ(X)=min{|Y|:Y⊆X,Y∈Fかつ$\forall{x}\in{X}\setminus{Y}$で$Y\cup{x}\not\in{F}$であるときランク商(rank quotient)を次のように定義する。

$q(E,F)=\min_{F\subseteq{F}}\frac{\rho(F)}{r(F)}$

独立性システム(E,F)のときq(E,F)≦1であり、マトロイド(E,F)のときq(E,F)=1である。なおかつ独立性システム(E,F)のときA∈Fとb∈Eに対してA∪{b}が高々p個しかサーキットを持たないならば1/q≦q(E,F)であることが知られているのでランク商を見積もることが可能である。

これにより、Eを辺集合、Fをマッチンググラフ集合とすると、q(E,F)≧1/2が得られる。これは、適当な辺を追加してできるのは高々長さ3のパスであるから、サーキットは2個しかできないのである。しかし、Eを点集合、Fを安定集合とするとq(E,F)はいくらでも小さくなる。なぜならば、スターグラフ(ネットワーク構成のスター型のようなグラフ)において、周囲の点を選べばそれは安定集合となるので、b∈Eとして中心の点を与えればサーキットは周囲の点の個数個になり、周囲の点数を無限に増やすことによってサーキットをいくらでも多くできるからである。また、マトロイドの場合q(E,F)=1であるので、任意のb∈Eを加えてもサーキットは高々1個しか持たない。例えば、Eを辺集合、Fを森集合とすると、森にどんな辺を加えても閉路は高々1個しか作れない。

他の公理系

集合Eとその部分集合の族Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなるようなFを得ることができる。

基の族

有限集合EとB⊆2^Eとする。Bがマトロイド(E,F)の基の族であるための必要十分条件は次の(B1)(B2)が成り立つことである。

• (B1)$B\neq\emptyset$
• (B2)任意の$B',B''\in{B},x{\in}B'{\setminus}B''$について$(B'\setminus\{x\})\cup\{y\}\in{B}$となる$y\in{B''}\setminus{B'}$が存在する。

基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えばE={1,2,3},B={{1,2},{2,3},{1,3}}とするとBは(B1)及び(B2)を満たす。このような基の族を持つマトロイドはk=2であるような一様マトロイドただ１つに決まることが分かる。また、基の族がB={{1,2},{3}}のときは(B2)を満たさない。よって、この基の族ではマトロイドにならない。事実、F={{1},{2},{3},{1,2}}は先の基の族になるが、(A3)を満たさずマトロイドになっていない。

サーキットの族

有限集合EとC⊆2^Eとする。Cがマトロイド(E,F)のサーキットの族であるための必要十分条件は次の(C1)(C2)(C3)が成り立つことである。

• (C1)$\emptyset\not\in{C}$
• (C2)任意のC₁,C₂∈CについてC₁⊆C₂ならばC₁=C₂である。
• (C3)任意のC₁,C₂∈CはC₁≠C₂でc∈C₁∩C₂とするとき、$C_3\subseteq(C_1{\cup}C_2)\setminus\{c\}$となるC₃∈Cが存在する。

ランク関数

マトロイドのランク関数は(R1)から(R6)を満たすが、逆にEと(R1),(R2),(R4)を満たす関数$r:2^E\to\mathbb{Z}_+$を与えればFは直ちに決まり(E,F)はマトロイドであり、rはランク関数である。

例えば、E={1,2,3}とし、関数rを

$r(\emptyset)=0,r({1})=1,r({2})=0,r({3})=1,r({1,2})=1,r({2,3})=1,$

$\ r({1,3})=2,r({1,2,3})=2\$

と定義すると、rは(R1),(R2),(R4)を満たすことが確認できる。すると、r(X)=|X|となるXの族をFと定義するとF={{1},{3},{1,3}}となり、(E,F)はマトロイドになることが確認できる。このように、rを決めれば対応するFがただ1つに決まる。

閉包関数

(L1)から(L4)を満たす関数$\sigma:2^E{\to}2^E$はマトロイドの閉包関数となる。

双対性

E={1,2,3}における双対の例。左上はマトロイドなのでその双対である右上もマトロイドである。左下は独立性システムなのでその双対である右下も独立性システムである。

独立性システム(E,F)の双対(dual)は(E,F^*)である。ただしF^*の要素fはEの部分集合であって、$f{\cap}b=\emptyset$となる(E,F)の基bが存在する。(E,F^**)=(E,F)であり、(E,F)がマトロイドであることと(E,F^*)はマトロイドであることは等価である。マトロイド(E,F)とその双対(E,F^*)とし、それぞれのランク関数をr,r^*とすると、r^*は任意のX⊆Eに対して

$r^*(X)=|X|+r(E{\setminus}X)-r(E)$

である。

例えばE={1,2,3},F={{1},{2},{1,2}}というマトロイドに対して基の族B={ {1,2} }だからF^*={ {3} }となる。双対のランク関数も、例えばr^*({1,3})=2+r({2})-r({1,2,3})=2+1-2=1となるように、成り立っていることが分かる。

グラフの双対

「双対」を参照すれば分かるとおり、数学における双対の概念は多方面にわたっている。実は、平面グラフに対する双対と閉路マトロイドの双対の概念は一致する。つまり、任意の平面的グラフGの閉路マトロイドM(G)は、当然双対を持つが、これはGの双対平面グラフG^*のマトロイドと(平面埋め込みの方法によらず)同一である。

組合せ理論

組合せ最適化問題は独立性システム(E,F)とコスト関数$c:F\to\mathbb{R}$を与えられたとき$\sum_{e\in{X}}c(e)$を最大にするX∈Fを求める最大化問題か、最小にする基を求める最小化問題に定式化できる。

例えば、

• 巡回セールスマン問題 - Eをグラフの辺、Fはハミルトン閉路の部分集合
• ナップサック問題 - Eを荷物、Fは規定の重さを超えない荷物の組み合わせ
• 最小全域木問題 - Eはグラフの辺、Fはグラフの森の集合

この中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。

次に、2つの貪欲法を示し、マトロイドにおいては最適解が得られることを示す。なお、コスト関数の単純な変換によって、最小化問題から最大化問題あるいはその逆にできるから、マトロイドにおいて2つのアルゴリズムどちらを使うかは問題ではない。

貪欲法

最良選択貪欲法

独立性システム(E,F)と$c:E\to\mathbb{R}_{+}$に対する最大化問題を解こう。最良選択貪欲法は、都合よいe∈Eから答えとなる集合に入れる。つまり、

1. c(e₁)≧c(e₂)≧…≧c(e_n)となるようにE={e₁,e₂,…,e_n}をソートする。
2. fという空集合を用意する。次のステップで解に含まれるe∈Eを入れていき、最終的に解をfとする。
3. For i=1 to n : f∪{e_i}∈Fならばfを新たにf∪{e_i}とする。

というアルゴリズムである。

最良選択貪欲法で得られる解のコストをG、最適解のコストをOPTとすると、ランク商q(E,F)を使って

$q(E,F)\le\frac{G}{OPT}{\le}1$

と書ける。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム(E,F)がマトロイドであるための必要十分条件は最良選択貪欲法で全ての$c:E\to\mathbb{R}_+$に対して最大化問題の最適解を求めることができることである。

最悪棄却貪欲法

次に独立性システム(E,F)と$c:E\to\mathbb{R}_{+}$に対する最小化問題を解こう。最悪棄却貪欲法は、都合の悪いe∈Eから解から除外する。つまり、

1. c(e₁)≧c(e₂)≧…≧c(e_n)となるようにE={e₁,e₂,…,e_n}をソートする。
2. f=Eとする。次のステップでfからコストの高い順にeを除去する。
3. For i=1 to n : $f\setminus\{e_i\}$が基を含むならば新たなfを$f\setminus\{e_i\}$とする。

というアルゴリズムである。

最悪棄却貪欲法で得られる解のコストをG、最適解のコストをOPTとすると、ランク商q(E,F)、双対な独立性システム(E,F^*)の下方ランク関数ρ^*、ランク関数r^*を使って

$1\le\frac{G}{OPT}\le\max_{X\subseteq{E}}\frac{|X|-\rho^*(X)}{|X|-r^*(X)}$

と書ける。マトロイドならばρ^*=r^*なので、常に最適解を得られることが分かる。

オラクル

組合せ最適化問題においてFは明示的に与えられることはまずない。Fを列挙しようとすることは無謀であるので、現実にはEとコスト関数cのみが与えられる。最良選択貪欲法を実行するには、さらに独立性オラクルを必要となる。独立性オラクルとは、X⊆Eが与えられたときX∈Fであるかどうかを判定するオラクルである。これがないと最良選択貪欲法の3番目のステップは実行できない。同様に最悪棄却貪欲法を実行するためにはX⊆Eが与えられたときXが基を含むかを判定する基拡張集合オラクルを必要とする。

では、独立性オラクルか基拡張集合オラクルどちらか一方が与えられたとき、そのオラクルを使ってもう一方を多項式時間で実行可能(多項式等価)だろうか。例えば、巡回セールスマン問題に対する独立性システムの独立性オラクルはつまり、与えられた辺集合がハミルトン閉路の部分集合であるかを判定するものであるが、グラフは完全グラフであるので、多項式時間で実行可能である。対して基拡張集合オラクルは与えられた辺集合からいくらか辺を削除することによってハミルトン閉路になるかということを判定しなくてはならない。それはつまりハミルトン閉路問題と等価であり、ハミルトン閉路問題はNP完全であるため難しいと言える。このように、独立性システムにおいて独立性オラクルと基拡張集合オラクルは必ずしも多項式等価ではない。

マトロイドにおいては独立性オラクル、基拡張集合オラクル、ランク関数を返すランクオラクル、閉包関数を返す閉包オラクル全て多項式等価である。しかし、与えられた部分集合が基かどうかを判定する基決定オラクルは独立性オラクルより弱いし、与えられた部分集合の最小元数の従属部分集合を返すオラクルは独立性オラクルより強い。

近似

最適化問題は厳密解を求めることが現実的でないことが多いために、近似の限界についても研究されている。次の問題が効率的に解ける(入力のサイズと1/εの多項式時間で解を出力するアルゴリズムが存在する)ことと、誤差が高々(1+ε)倍の解を出力する多項式時間アルゴリズムが存在することは同値である。

独立性システム(E,F)、コスト関数$c:E\to\mathbb{Z}_+$、部分集合S,S'⊆E、ε>0が

$\frac{1}{1+\epsilon}c(S){\le}c(S'){\le}(1+\epsilon)c(S)$

であるとき、S⊆Bとなる基Bが存在してS'⊆B'となる基B'全てに対して(1+ε)c(B)≧c(B')が成立するか？

つまり、部分的なコスト(c(S)やc(S'))が高々(1+ε)倍違う程度ならば、それらからできうる最適解も(1+ε)倍程度しか違わないだろうか、という問題である。部分が最適ならば全体も最適であるという場合はε=0であり、よく知られているように動的計画法が存在する。よって、(E,F)をマトロイドに限定するならば多項式時間アルゴリズムは存在する。

ナップサック問題はこのアルゴリズムが知られている珍しい例で、計算時間が$O(n^2\cdot\frac{1}{\epsilon})$や$O(n\log(\frac{1}{\epsilon})+\frac{1}{\epsilon^4})$で、出力される解の評価が最適解の評価の高々(1+ε)倍であるアルゴリズムがある。

マトロイドの交差・分割

今までは具体的な問題を独立性システムやマトロイドに一般化して様々な定理を得てきたが、ここでは独立性システム間に関する様々な考察を取り上げる。

交差

2つの独立性システム(E,F),(E,F')とするとき、(E,F∩F')を2つの独立性システムの交差(intersection)と呼ぶ。任意の独立性システム(E,F)はp個のマトロイドの交差で表せ、ランク商q(E,F)≧1/pであるので、最良選択貪欲法での解を見積もることができる。専ら興味が持たれるのは2つのマトロイドの交差である。例えば2部グラフのマッチング問題を考えよう。Eを辺集合、Fをマッチング集合とすれば、2部グラフだから点集合はA∪Bと書ける。F₁を任意の点a∈Aに繋がる辺は高々1本であるという条件とするならば(E,F₁)はマトロイドであり、同様にF₂を任意の点b∈Bに繋がる辺は高々1本であるという条件とするならば(E,F₂)もマトロイドである。F=F₁∩F₂なので、(E,F)は2つのマトロイド(E,F₁),(E,F₂)の交差である。

• マトロイド交差問題(Matroid Intersection Problem) - 2つのマトロイド(E,F₁),(E,F₂)が与えられたとき、|F|が最大となるようなF∈F₁∩F₂を求めよ。

2つのマトロイド(E,F₁),(E,F₂)のランク関数をそれぞれr₁,r₂とすると、

$max\{|X|:X{\in}F_1{\cap}F_2\}=min\{r_1(W)+r_2(E\setminus{W}):W\subseteq{E}\}$

となる。マトロイド交差問題は多項式時間で解けるが、3つのマトロイドを考えるとそれはNP困難問題である。

重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方をαとするとO(|E|³α)で解ける。

分割

k個のマトロイド(E,F₁),...,(E,F_k)についてX⊆EはX=X₁∪…∪X_kとなるようなX_i∈F_i(i=1,...,k)が存在するとき、分割可能(partitionable)と呼ぶ。また、Fが分割可能ならば(E,F)は(E,F₁),...,(E,F_k)の合併(union)あるいは和(sum)と呼ばれる。

マトロイドの交差は、必ずしもマトロイドにはならなかったが、マトロイドの合併はマトロイドになる。k個のマトロイド(E,F₁),...,(E,F_k)の各ランク関数をr₁,...,r_kとすると、これらの合併(E,F)のランク関数は

$r(X)=\min_{A{\subseteq}X}(|X\setminus{A}|+\sum_{i=1}^kr_i(A))$

である。

次の問題とマトロイド交差問題は等価である。

• マトロイド分割問題(Matroid Partitioning Problem) - k個のマトロイド(E,F₁),...,(E,F_k)が与えられたとき|X|が最大になるような分割可能なX⊆Eを答えよ。

一般化

(詳細は各項目を参照のこと)

グリードイドはマトロイドと反マトロイドを一般化したものである。グリードイドにも貪欲法が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題はNP困難であることが知られている。

また、マトロイドのランク関数が劣モジュラー関数であることは既に述べたが、有限集合Eと劣モジュラー関数$f:2^E\to\mathbb{R}_+$を用いてポリマトロイド(polymatroid)と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラー関数最小化問題に帰着できる。劣モジュラー関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラー関数最小化問題は楕円体法を用いることで多項式時間で解けることが知られて以来、Schrijverのアルゴリズム等が知られている。

参考文献

1. B.コルテ・J.フィーゲン 『組合せ最適化-理論とアルゴリズム』 浅野孝夫,平田富夫,小野孝男,浅野泰仁訳、シュプリンガー・ジャパン、2005年11月3日、初版。ISBN 4-431-71183-X。

関連項目

• 組合せ最適化
• グラフ理論
• 計算複雑性理論
• ポリマトロイド
• 劣モジュラー関数