マトロイド
マトロイド(matroid)は、ある公理を満たす集合とそのべき集合の部分集合の組である。歴史的には、行列の一次独立・従属を一般化した概念であるが、多くの組合せ最適化問題をマトロイドあるいはより緩い独立性システムとコスト関数で定式化でき、特徴付けを行える等応用範囲は広い。特に組合せ最適化において、マトロイド上の最適化問題には単純な貪欲法によって多項式時間のアルゴリズムとは限らないものの最適解が得られることは非常に重要である。
有限集合 E とその部分集合族 F \subseteq 2^E の組 (E, F) が
(A1) \emptyset\in{F}
(A2) X \subseteq Y \in F \Rightarrow X \in F
(A3) X, Y \in F,\ |X|>|Y| \Rightarrow \exists\ x \in X \setminus Y \text{ s.t. } Y \cup \{x\} \in F.
を満たすとき、マトロイドと呼ばれ、(A1) 及び (A2) のみを満たすとき独立性システム(independence system)と呼ばれる。さらに (A1) 及び (A3) を満たすときグリードイド(greedoid)と呼ばれる。
以下に本項で使う用語の定義を挙げる。
独立集合 (independent set) - F の要素
従属集合 (dependent set) - 2^E \setminus F の要素
サーキット (circuit) - 極小な従属集合
基 (base, basis) - 極大な独立集合
Xの基 - X \subseteq E とする X の部分集合の中で極大な独立集合
独立性システム (E,F) の階数 (rank) 関数 r: 2^E \to \mathbb{R} は、X \subseteq Eに対して
r(X) := \max \{ |Y| : Y \subseteq X,Y \in F \}
と定義される。マトロイドならば、公理(A3) からEの部分集合Xに対してXのどの基も元数は等しいため、階数関数をXの基の大きさと定義しても構わない。
例えば、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等となる。
独立性システム (E,F) の階数関数 r: 2^E \to \mathbb{R} は任意のX,Y \subseteq Eとx,y \in Eについて次の性質を持つ。
(R1) r(X) \leq |X|
(R2) X \subseteq Y \Rightarrow r(X) \le r(Y)
(R3) r(\emptyset)=0
さらに、(E,F) がマトロイドならば次の性質も持つ。
(R4) r(X \cup Y)+r(X \cap Y) \leq r(X) + r(Y)
(R5) r(X) \leq r(X \cup \{x\}) \leq r(X)+1
(R6) r(X \cup \{x\}) = r(X \cup \{y\}) = r(X) \Rightarrow r(X \cup \{x,y\})=r(X)
特に(R4)に示されているように、階数関数が劣モジュラであることは、マトロイドの極めて重要な性質である。
独立性システム (E,F) の閉包 (closure) 関数 \sigma \colon 2^E \to 2^E は、  X \subseteq E に対して
\sigma (X) := \{ y \in E : r(X \cup {y}) = r(X) \}
で定義される。
\sigma(X) を X の閉包と呼ぶ。
マトロイド (E,F) の閉包関数 \sigma\colon 2^E \to 2^E は次の性質を持つ。
(L1) 任意の X \subseteq E に対して、  X \subseteq \sigma(X)
(L2) 任意の X, Y \subseteq E に対して、  X \subseteq Y \Rightarrow \sigma(X) \subseteq \sigma(Y)
(L3) 任意の X \subseteq E に対して、  \sigma(X) = \sigma(\sigma(X))
(L4) 任意の  X, Y \subseteq E と任意の  x,y \in E に対して、  y \not\in \sigma(X),\ y \in\sigma(X\cup\{x\}) \Rightarrow x \in \sigma(X \cup \{y\})
下方ランク (lower rank) 関数 \rho(X) を X に含まれる基の最小元数とする。つまり、
\rho(X) := \min \{ |Y|:Y \subseteq X, Y \in F かつ  \forall{x} \in X \setminus Y に対し Y \cup \{x\} \not\in F \}
と定義する。すると、ランク商 (rank quotient) は次のように定義される。
q(E,F):=\min_{X\subseteq{E}\frac{\rho(X)}{r(X)}
マトロイドのとき q(E,F)=1 である。独立性システムのとき q(E,F) \le 1 であり、 A \in F, b \in E に対してA \cup \{b\} が高々p 個しかサーキットを持たないならば 1/p \le q(E,F) であることが知られているのでランク商を見積もることが可能である。
Eを有限集合とし、ある整数r以下の要素数を持つ2Eの部分集合をFとするとき、(E,F)はマトロイドとなる。これを、一様マトロイド (uniform matroid)と呼び、n=|E|としたときU_n^rなどと書く。U_n^rにおける基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和は分割マトロイド (partition matroid)と呼ばれる。具体的には、B_1,\ldots,B_kを互いに素な集合とし、それぞれに0 \le d_i \le |B_i| (0 \le i \le k)を定めたとき、0 \le i \le kそれぞれにおいて|I\cap B_i|\le d_iを満たすようなI\subset \bigcup_i B_iの集合をFとすれば、マトロイドとなる。
Eを無向グラフGの辺集合、Fを森の集合とするとき、(E,F)はマトロイドとなり、グラフ的マトロイド (graphic matroid) または 閉路マトロイド (cycle matroid)と呼ぶ。しばしばグラフGがグラフ的マトロイドであることをM(G)と書く。グラフ的マトロイドにおける従属集合は、閉路を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また(Xの)基とは(Xの部分集合の中で)できうる最大の森のことで、明らかに(Xでカバーされる)点の数-1本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数はr(X)=(Xがカバーする点数)-1と書ける。
他にも、グラフにおけるマトロイドはいくつか知られている。
Eを無向グラフGの辺集合、Fを(G, X)がpseudoforestとなるようなXの集合とするとき(E,F)はマトロイドとなる。これを、bicircularマトロイド(bicircular matroid)と呼ぶ。
点集合U,V、辺集合Xとする2部グラフG = (U,V,X)において、マッチングの端点となる点集合S \subseteq Uを要素とする集合をFとするとき、(U,F)はマトロイドとなる。これを、横断マトロイド(transversal matroid)と呼ぶ。完全2部グラフK_{n,r}の横断マトロイドは、一様マトロイドU_n^rである。
点集合をVとするグラフにおいて、点の部分集合をV',U \subseteq Vとする。Uへの点素な|U|本の道が存在するV'の部分集合をFの要素とすると、(V', F)はマトロイドとなる。これを、ガンモイド (gammoid)と呼ぶ。特に、(V, F)を狭義ガンモイド(strict gammoid)と呼ぶ。
Eを体上の行列の列集合、その体上で線形独立である列の集合をFとするとき、(E,F)はマトロイドとなり、ベクトルマトロイド (vector matroid)と呼ぶ。マトロイドが同等の体K上のベクトルマトロイドとして記述できるとき、表現可能であると呼ばれる。任意の体上で表現可能なマトロイドを正則マトロイド(regular matroid)と呼び、位数2の有限体上で表現可能なマトロイドを2値マトロイド (binary matroid)と呼ぶ。これらは、
マトロイド ⊃ 2値マトロイド ⊃ 正則マトロイド ⊃ グラフ的マトロイド
という包含関係が成り立つ。一方で、Fanoマトロイドは、2値マトロイドであるが(実数体上では表現できないため)正則マトロイドではない。また、Vámosマトロイド (Vámos matroid)は、任意の体上で表現できないマトロイドの最も簡単な例である。
2部マトロイド(bipartite matroid)は、サーキットの大きさがすべて偶数であるようなマトロイドである。2部グラフのグラフ的マトロイドを一般化しており、グラフ的マトロイドが2部マトロイドであることと、グラフが2部グラフであることは同値である。
シルベスターマトロイド(Sylvester matroid)は、すべてのサーキットの大きさが3であるようなマトロイドである。例えば、ランク2の一様マトロイドU_n^2はシルベスターマトロイドである。
pavingマトロイド(paving matroid)は、すべてのサーキットの大きさがランクよりも大きいマトロイドである。例えば、一様マトロイドU_n^rのランクはrであり、サーキットの大きさは常にr+1であるため、pavingマトロイドである。
オイラーマトロイド(eulerian matroid)は、要素がサーキットによって分割できるようなマトロイドである。例えば、一様マトロイドU_n^rはr+1がnを割り切るとき、かつそのときのみオイラーマトロイドである。
集合Eとその部分集合の族Fが(A1)から(A3)を満たすときマトロイドと呼ぶことにし、そこから基やランクを定義した。だが、実はこれらの性質を持つ族あるいは関数からマトロイドとなるようなFを得ることができる。
有限集合 E と \mathcal{B} \subseteq 2^E とする。
\mathcal{B} がマトロイド (E,F) の基族であるための必要十分条件は次の(B1),(B2)が成り立つことである。
(B1) \mathcal{B}\neq\emptyset
(B2) 任意のB',B\in \mathcal{B}, x \in B' \setminus B について (B'\setminus \{ x \}) \cup \{ y \} \in \mathcal{B} となる y \in {B} \setminus {B'} が存在する。
基が1つしかない場合は明らかにマトロイドとなる。そうでない場合、例えば  E = \{ 1,2,3 \}, \mathcal{B} = \{\{1,2\},\{2,3\},\{1,3\}\} とすると \mathcal{B} は(B1)及び(B2)を満たす。このような基の族を持つマトロイドは、一様マトロイド U_3^2 ただ1つに決まることが分かる。また、基族が \mathcal{B}=\{\{1,2\},\{3\}\}のときは(B2)を満たさないため、この基族ではマトロイドにならない。事実、 F = \{\{1\}, \{2\}, \{3\}, \{1,2\}\} とすると、この例の基族となるが、(A3)を満たさずマトロイドになっていない。
有限集合 E と C⊆2E とする。C がマトロイド (E,F) のサーキットの族であるための必要十分条件は次の(C1),(C2),(C3)が成り立つことである。
(C1) \emptyset\not\in{C}
(C2) 任意のC1,C2∈C について C1⊆C2 ならば C1=C2 である。
(C3) 任意の C1,C2∈C は C1≠C2 で c∈C1∩C2 とするとき、C_3 \subseteq (C_1 \cup C_2) \setminus \{c \} となる C3∈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 はマトロイドの閉包関数となる。
ここでは、1つ以上のマトロイド(あるいは独立性システム)から新たなマトロイドを構成する方法について説明する。
独立性システム (E,F) に対して、 F* を X \cap B = \emptyset となる (E,F) の基 B が存在するような X \subseteq Eの集合とする。このとき、 (E, F*) を (E,F) の双対(dual)と定義する。
双対には次のような性質がある。
(E, F**) = (E,F)
(E, F) が独立性システムならば、(E, F*) は独立性システム
(E,F) はマトロイド \iff (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* のマトロイドと(平面埋め込みの方法によらず)同一である。
2つの独立性システム (E,F1),(E,F2) とするとき、(E,F1∩F2)を2つの独立性システムの交差(intersection)と定義する。有限個の独立性システムの交差も同様に定義でき、交差もまた独立性システムとなる。任意の独立性システム (E,F) は、有限個のマトロイドの交差で表せる。さらに、p 個のマトロイドの交差ならば、 q(E,F)≧1/p 。
例えば2部グラフのマッチング問題の場合、Eを辺集合、Fをマッチング集合とすれば、2部グラフであるから点集合はA∪Bと書ける。F1を任意の点a∈Aに繋がる辺は高々1本であるという条件とするならば(E,F1)はマトロイドであり、同様にF2を任意の点b∈Bに繋がる辺は高々1本であるという条件とするならば(E,F2)もマトロイドである。F=F1∩F2なので、(E,F)は2つのマトロイド(E,F1),(E,F2)の交差である。
2つのマトロイド (E,F1),(E,F2) とする。 X1∈F1, X2∈F2 となるような X の分割 X=X1∪X2 が存在するとき、 X⊆E は 分割可能(partitionable)であると呼ぶ。F=\{X\subseteq E : X \mbox{ is partitionable}\}とするとき、(E,F) を (E,F1),(E,F2) の合併(union)あるいは和(sum)と呼ぶ。有限個のマトロイドの合併も同様に定義できる。
マトロイドの合併は、マトロイドとなる。
k個のマトロイド(E,F1),...,(E,Fk)の各ランク関数をr1,...,rkとすると、これらの合併(E,F)のランク関数は r(X)=\min_{A{\subseteq}X}(|X\setminus{A}|+\sum_{i=1}^kr_i(A)) である。
組合せ最適化問題の多くは、独立性システム (E,F) とコスト関数 c : E \to \mathbb{R} に対して、\sum_{e \in X}c(e) を最大(あるいは最小)にする X \in F を求める最適化問題に定式化できる。
例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。
巡回セールスマン問題 - Eをグラフの辺、Fはハミルトン閉路の部分集合
ナップサック問題 - Eを荷物、Fは規定の重さを超えない荷物の組合せ
最小全域木問題 - Eはグラフの辺、Fはグラフの森の集合
マトロイドにおいては貪欲法で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、クラスカル法はマトロイド上の貪欲法で説明できるが、プリム法やダイクストラ法は異なる。
最良選択貪欲法は、c(e) の大きい順に e \in E を暫定解に追加できるならば追加し,追加できない場合は次の要素に移ることを繰り返すアルゴリズムである。つまり、
c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n) となるように E = \{e_1, e_2, \cdots, e_n\} をソートする。
E_{ans} \leftarrow \emptyset
For i = 1 to n : E_{ans} \cup \{ e_i \} \in F ならば E_{ans} \leftarrow E_{ans} \cup \{ e_i \}
E_{ans}を解として出力する。
というアルゴリズムである。
最良選択貪欲法で得られる解のコストを c(G) 、最適解のコストを c(OPT) とすると、ランク商 q(E,F) を使って
q(E,F) \le \frac{c(G)}{c(OPT)} \le 1
が任意のコスト関数に対して成立する。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム(E,F)がマトロイドであるための必要十分条件は最良選択貪欲法で全てのc:E\to\mathbb{R}_+に対して最大化問題の最適解を求めることができることである。これを Edmonds-Rado 定理という。
c(G) \ge q(E,F)c(OPT) の証明の概要を述べる。
G を最良選択貪欲法で得られる解、 OPT を最適解とする。 E=\{e_1,\ldots,e_n\} は、 c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n) となるようにソート済みであるとし、E_j=\{e_1,\ldots,e_j\} とする。また、
d_j =
\begin{cases}
c(e_n), &\mbox{if } j = n\\
c(e_j) - c(e_{j+1}), &\mbox{otherwise}
\end{cases}
とし、任意の X \subseteq 2^E に対して、 X_j = X \cap E_jと置く。このとき、次の事実が成り立つ。
任意の X \subseteq 2^E において、 c(X) = \sum_{j=1}^n |X_j| d_j
任意の 1\le j \le n において、 \rho(E_j) \le |G_j|
任意の X \subseteq E において、 r(X)q(E,F) \le \rho(X)
任意の 1\le j \le n において、 |OPT_j| \le r(E_j)
以上のことから、
c(G) = \sum_{j=1}^n |G_j| d_j \ge \sum_{j=1}^n \rho(E_j) d_j \ge q(E,F)\sum_{j=1}^n r(E_j) d_j \ge q(E,F)\sum_{j=1}^n |OPT_j| d_j = q(E,F)c(OPT)
となる。
独立性システム (E,F) とコスト関数 c:E\to\mathbb{R}_{+}に対する最小化問題を解く。最悪棄却貪欲法は、都合の悪い e∈E を優先して解から除外する。つまり、
c(e_1) \ge c(e_2) \ge \cdots \ge c(e_n) となるように E = \{e_1, e_2, \cdots, e_n\} をソートする。
E_{ans}\leftarrow E
For i = 1 to n : E_{ans}\setminus\{e_i\}が基を含むならば、E_{ans}\leftarrow E_{ans}\setminus\{e_i\}
E_{ans}を解として出力する。
というアルゴリズムである。
最悪棄却貪欲法で得られる解のコストを c(G) 、最適解のコストを c(OPT) とすると、ランク商 q(E,F) 、双対な独立性システム(E,F*)の下方ランク関数ρ*、ランク関数r*を使って
1\le\frac{c(G)}{c(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+ε)倍であるアルゴリズムがある。
マトロイド交差問題(Matroid Intersection Problem)は、2つのマトロイド(E,F1),(E,F2)が与えられたとき、|F|が最大となるようなF∈F1∩F2を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これはNP困難問題である。
重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方をαとするとO(|E|3α)で解ける。
マトロイド分割問題(Matroid Partitioning Problem)は k 個のマトロイド (E,F1),...,(E,Fk) が与えられたとき |X| が最大になるような分割可能な X⊆E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。
グリードイドはマトロイドと反マトロイドを一般化したものである。グリードイドにも貪欲法が定式化できて、特殊な条件下においては最適解を出力する。だが、グリードイド上での最適化問題はNP困難であることが知られている。
また、マトロイドのランク関数が劣モジュラ関数であることは既に述べたが、有限集合Eと劣モジュラ関数f:2^E\to\mathbb{R}_+を用いてポリマトロイド(polymatroid)と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は楕円体法を用いることで多項式時間で解けることが知られて以来、Schrijverのアルゴリズム等が知られている。