マトロイド

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

定義

有限集合 E とその部分集合族 $F\subseteq 2^{E}$ の組 (E, F) が^{[注 1]}

(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)\leq 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)\leq 1$ であり、 $A\in F,b\in E$ に対して $A\cup \{b\}$ が高々p 個しかサーキットを持たないならば $1/p\leq q(E,F)$ である^[1]ことが知られているのでランク商を見積もることが可能である。

例

一様マトロイド

E を有限集合とし、ある整数 r 以下の要素数を持つ 2^E の部分集合をFとするとき、(E, F) はマトロイドとなる。これを、一様マトロイド（英語版） (uniform matroid) と呼び、n=|E|としたとき $U_{n}^{r}$ などと書く。 $U_{n}^{r}$ における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和は分割マトロイド（英語版） (partition matroid) と呼ばれる^{[注 2]}。具体的には、 $B_{1},\ldots ,B_{k}$ を互いに素な集合とし、それぞれに $0\leq d_{i}\leq |B_{i}|\ (0\leq i\leq k)$ を定めたとき、 $0\leq i\leq k$ それぞれにおいて $|I\cap B_{i}|\leq d_{i}$ を満たす $I\subset \bigcup _{i}B_{i}$ の集合を F とすれば、マトロイドとなる。

グラフ理論におけるマトロイド

E を無向グラフGの辺集合、F を森^{[注 3]}の集合とするとき、(E, F) はマトロイドとなり、グラフ的マトロイド（英語版） (graphic matroid) または 閉路マトロイド (cycle matroid) と呼ぶ。しばしばグラフGがグラフ的マトロイドであることを M(G) と書く。グラフ的マトロイドにおける従属集合は、閉路を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また（X の）基とは（X の部分集合の中で）できうる最大の森のことで、明らかに（X でカバーされる）点の数 − 1 本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数は r(X) = (Xがカバーする点数) − 1 と書ける。

他にも、グラフにおけるマトロイドはいくつか知られている。

E を無向グラフ G の辺集合、F を (G, X) がpseudoforest（英語版）^{[注 4]}となるような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 ⊆ 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)を満たす^{[注 5]}関数 $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^*) はマトロイド^[2]。
マトロイド (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, F₁), (E, F₂) とするとき、(E, F₁ ∩ F₂) を2つの独立性システムの交差 (intersection) と定義する。有限個の独立性システムの交差も同様に定義でき、交差もまた独立性システムとなる。任意の独立性システム (E, F) は、有限個のマトロイドの交差で表せる。さらに、p 個のマトロイドの交差ならば、q(E, F) ≧ 1/p。

例えば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₂) の交差である。

合併

2つのマトロイド (E, F₁),(E, F₂) とする。X₁ ∈ F₁, X₂ ∈ F₂ となる X の分割 X = X₁ ∪ X₂ が存在するとき、X ⊆ E は 分割可能 (partitionable) であると呼ぶ。 $F=\{X\subseteq E:X{\mbox{ is partitionable}}\}$ とするとき、(E, F) を (E, F₁), (E, F₂) の合併(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}^{k}r_{i}(A))$ である^[3]。

組合せ最適化

組合せ最適化問題の多くは、独立性システム $(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})\geq c(e_{2})\geq \cdots \geq 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)\leq {\frac {c(G)}{c(OPT)}}\leq 1

が任意のコスト関数に対して成立する^[4]^[5]。マトロイドのランク商は1なので、マトロイドである最大化問題は最良選択貪欲法によって最適解を得られる。これは逆も言えるので、独立性システム (E, F) がマトロイドであるための必要十分条件は最良選択貪欲法で全ての $c:E\to \mathbb {R} _{+}$ に対して最大化問題の最適解を求めることができることである^[6]^[7]。これを Edmonds-Rado 定理という。

証明の概要

$c(G)\geq q(E,F)c(OPT)$ の証明の概要を述べる。

G を最良選択貪欲法で得られる解、 $OPT$ を最適解とする。 $E=\{e_{1},\ldots ,e_{n}\}$ は、 $c(e_{1})\geq c(e_{2})\geq \cdots \geq 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}$ ^{[注 6]}
任意の $1\leq j\leq n$ において、 $\rho (E_{j})\leq |G_{j}|$ ^{[注 7]}
任意の $X\subseteq E$ において、 $r(X)q(E,F)\leq \rho (X)$ ^{[注 8]}
任意の $1\leq j\leq n$ において、 $|OPT_{j}|\leq r(E_{j})$ ^{[注 9]}

以上のことから、

c(G)=\sum _{j=1}^{n}|G_{j}|d_{j}\geq \sum _{j=1}^{n}\rho (E_{j})d_{j}\geq q(E,F)\sum _{j=1}^{n}r(E_{j})d_{j}\geq 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})\geq c(e_{2})\geq \cdots \geq 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\leq {\frac {c(G)}{c(OPT)}}\leq \max _{X\subseteq {E}}{\frac {|X|-\rho ^{*}(X)}{|X|-r^{*}(X)}}

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

オラクル

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

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

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

近似

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

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

{\frac {1}{1+\epsilon }}c(S)\leq c(S')\leq (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 }})$ ^[12]^[13]^[14]や $O(n\log({\frac {1}{\epsilon }})+{\frac {1}{\epsilon ^{4}}})$ ^[15]で、出力される解の評価が最適解の評価の高々 1 + ε 倍であるアルゴリズムがある。

マトロイドに関する問題

マトロイド交差問題と分割問題

マトロイド交差問題 (Matroid Intersection Problem) は、2つのマトロイド (E, F₁), (E, F₂) が与えられたとき、|F| が最大となるような F ∈ F₁ ∩ F₂ を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これはNP困難問題である。

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

マトロイド分割問題 (Matroid Partitioning Problem) は k 個のマトロイド (E, F₁), …, (E, F_k) が与えられたとき |X| が最大になるような分割可能な X ⊆ E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。

一般化

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

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

脚注

[脚注の使い方]

注釈

^ 記号の意味については「冪集合」「空集合」「集合間の関係を表す記号」「濃度 (数学)」「和集合」「差集合」を参照のこと
^ マトロイドの直和もマトロイドになる。
^ 閉路のない辺集合
^ 各連結成分において、高々1つの閉路を持つグラフ
^ (R3),(R5),(R6)を満たす関数と(R1),(R2),(R4)を満たす関数は同値
^ $(|X_{j}|-|X_{j-1}|)$ は、 $e_{j}\in X$ のとき、かつそのときのみ1となるから、 $c(X)=\sum _{j=1}^{n}(|X_{j}|-|X_{j-1}|)c(e_{j})$ が得られる。これを $|X_{j}|$ でまとめて右辺を得る。
^ G_j は E_j の基であり、ρ の定義より得られる。
^ ランク商の定義より明らか。
^ $OPT_{j}\in F$ であることと、階数関数の定義および性質(R1)より得られる。
^ X の基でないことに注意
^ 概念は「多項式時間変換」に詳しい
^ 最良選択貪欲法を使うことによって（本質的には独立性オラクルを複数回使うことによって）基決定オラクルを作れるが、逆に基決定オラクルを多項式回使っても独立性オラクルを作れない

出典

^ D. Hausmann; B. Korte , T. A. Jenkyns (1980). “Worst case analysis of greedy type algorithms for independence systems”. Mathematical Programming Studies 12: 120-131.
^ Hassler Whitney (1935-07). “On the abstract properties of linear dependence” (pdf). American Journal of Mathematics 57: 509-533. http://www.math.osu.edu/~chmutov/wor-gr-su06/ref/Wh.pdf 2011年3月19日閲覧。.
^ Crispin Nash-Williams (1967). “An application of matroids to graph theory”. In P.Rosenstiehl, ed.. Theory of Graphs; proceedings of an international symposium in Rome 1966. New York: Gordon and Breach. pp. 263-265
^ T.A. Jenkyns (1976). “The Efficacy of the greedy Algorithm”. Proc. of 7th S-E. Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg: 341-350.
^ Bernhard Korte; Dirk Hausmann (1978). “An Analysis of the greedy heuristic for independence systems”. In B. Alspach, P. Hell, D.J. Miller, eds.. Aogorithmic Aspects of Combinatorics; Annals of Discrete Mathematics. 2. Amsterdam: North-Holland. pp. 65-74
^ R. Rado (1957). “Note on Independence Functions”. Proceedings of the London Mathematical Society 7: 300-320.
^ Jack Edmonds (1971). “Matroids and the greedy algorithm”. Mathematical Programming 1: 127-136.
^ Bernhard Korte; C.L. Monma (1979). “Some remarks on a classification of oracle-type algorithms”. In L. Collatz, G. Meinardus, W. Wetterling, eds.. Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen. 2. Basel: Birkhäuser. pp. 195-215
^ Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”. In R. E. Miller and J. W. Thatcher eds. Complexity of Computer Computations. New York: Plenum. pp. 85-103
^ D. Hausmann; B. Korte (1981). “Algorithmic versus axiomatic definitions of matroids”. Mathematical Programming Study 14: 98-111.
^ B. Korte; R. Schrader (1981). “On the existence of fast approximation schemes”. In O. Mangaserian, R.R. Meyer, S.M. Robinson, eds.. Nonlinear Programming. New York: Academic Press. pp. 415-437
^ Oscar H. Ibarra; Chul E. Kim (1975-10). “Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems”. Journal of the ACM 22 (4): 463-468. doi:10.1145/321906.321909. ISSN 0004-5411.
^ Sartaj K. Sahni (1976-01). “Algorithms for Scheduling Independent Tasks”. Journal of the ACM 23 (1): 116-127. doi:10.1145/321921.321934. ISSN 0004-5411.
^ G.V. Gens (1979). “Computational complexity of approximation algorithms for combinatorial problems”. In J. Becvar, ed.. Mathematical Foundations of Computer Science. Berlin: Springer. pp. 292-300
^ Eugene L. Lawler (1979). “Fast Approximation Algorithms for Knapsack Problems”. Mathematics of Operations Research 4: 339-356. doi:10.1287/moor.4.4.339.
^ A. Frank (1981). “A weighted matroid intersection algorithm”. Journal of Algorithms 2: 328-336.
^ M. Grötschel; L. Lovász, A. Schrijver (1981). “The ellipsoid method and its consequences in combinatorial optimization” (pdf). Combinatorica 1: 169-197. http://oai.cwi.nl/oai/asset/10046/10046A.pdf 2011年3月26日閲覧。.
^ Alexander Schrijver (2000). “A combinatorial algorithm minimizing submodular functions in strongly polynomial time” (pdf). Journal of Combinatorial Theory, Series B 80 (2): 346-355. https://homepages.cwi.nl/~lex/files/minsubm6.pdf 2023年5月14日閲覧。.

参考文献

B.コルテ、J.フィーゲン著、浅野孝夫、平田富夫、小野孝男、浅野泰仁訳『組合せ最適化-理論とアルゴリズム』（第2版）シュプリンガー・ジャパン、2012年2月29日。ISBN 978-4621062029。

外部リンク

『マトロイドの定義と具体例』 - 高校数学の美しい物語