マトロイド 📖 Wikipedia

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

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

• (A1) ${\displaystyle \emptyset \in {F}}$
• (A2) ${\displaystyle X\subseteq Y\in F\Rightarrow X\in F}$
• (A3) ${\displaystyle 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) - ${\displaystyle F}$ の要素
• 従属集合 (英: dependent set) - ${\displaystyle 2^{E}\setminus F}$ の要素
• サーキット (英: circuit) - 極小な従属集合
• 基 (英: base, basis) - 極大な独立集合
• ${\displaystyle X}$ の基 - ${\displaystyle X\subseteq E}$ とする ${\displaystyle X}$ の部分集合の中で極大な独立集合

独立性システム (E, F) の階数 (rank) 関数 ${\displaystyle r:2^{E}\to \mathbb {R} }$ は、${\displaystyle X\subseteq E}$ に対して

${\displaystyle r(X):=\max\{|Y|:Y\subseteq X,Y\in F\}}$

と定義される。マトロイドならば、公理(A3) から E の部分集合 X に対して X のどの基も元数は等しいため、階数関数を${\displaystyle 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 等となる。

独立性システム ${\displaystyle (E,F)}$ の階数関数 ${\displaystyle r:2^{E}\to \mathbb {R} }$ は任意の ${\displaystyle X,Y\subseteq E}$ と ${\displaystyle x,y\in E}$ について次の性質を持つ。

• (R1) ${\displaystyle r(X)\leq |X|}$
• (R2) ${\displaystyle X\subseteq Y\Rightarrow r(X)\leq r(Y)}$
• (R3) ${\displaystyle r(\emptyset )=0}$

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

• (R4) ${\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)}$
• (R5) ${\displaystyle r(X)\leq r(X\cup \{x\})\leq r(X)+1}$
• (R6) ${\displaystyle r(X\cup \{x\})=r(X\cup \{y\})=r(X)\Rightarrow r(X\cup \{x,y\})=r(X)}$

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

独立性システム ${\displaystyle (E,F)}$ の閉包 (closure) 関数 ${\displaystyle \sigma \colon 2^{E}\to 2^{E}}$ は、${\displaystyle X\subseteq E}$ に対して

${\displaystyle \sigma (X):=\{y\in E:r(X\cup {y})=r(X)\}}$

で定義される。 ${\displaystyle \sigma (X)}$ を X の閉包と呼ぶ。

マトロイド ${\displaystyle (E,F)}$ の閉包関数 ${\displaystyle \sigma \colon 2^{E}\to 2^{E}}$ は次の性質を持つ。

• (L1) 任意の ${\displaystyle X\subseteq E}$ に対して、${\displaystyle X\subseteq \sigma (X)}$
• (L2) 任意の ${\displaystyle X,Y\subseteq E}$ に対して、${\displaystyle X\subseteq Y\Rightarrow \sigma (X)\subseteq \sigma (Y)}$
• (L3) 任意の ${\displaystyle X\subseteq E}$ に対して、${\displaystyle \sigma (X)=\sigma (\sigma (X))}$
• (L4) 任意の ${\displaystyle X,Y\subseteq E}$ と任意の ${\displaystyle x,y\in E}$ に対して、${\displaystyle y\not \in \sigma (X),\ y\in \sigma (X\cup \{x\})\Rightarrow x\in \sigma (X\cup \{y\})}$

下方ランク (lower rank) 関数 ${\displaystyle \rho (X)}$ を ${\displaystyle X}$ に含まれる基の最小元数とする。つまり、

${\displaystyle \rho (X):=\min\{|Y|:Y\subseteq X,Y\in F}$ かつ ${\displaystyle \forall {x}\in X\setminus Y}$ に対し ${\displaystyle Y\cup \{x\}\not \in F\}}$

と定義する。すると、ランク商 (rank quotient) は次のように定義される。

${\displaystyle q(E,F):=\min _{X\subseteq {E}}{\frac {\rho (X)}{r(X)}}}$

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

E を有限集合とし、ある整数 r 以下の要素数を持つ 2^E の部分集合をFとするとき、(E, F) はマトロイドとなる。これを、一様マトロイド（英語版） (uniform matroid) と呼び、n=|E|としたとき ${\displaystyle U_{n}^{r}}$ などと書く。${\displaystyle U_{n}^{r}}$ における基は、要素数がrであるようなEの部分集合であり、サーキットは要素数がr+1であるようなEの部分集合である。また、一様マトロイドの直和は分割マトロイド（英語版） (partition matroid) と呼ばれる^{[注 2]}。具体的には、${\displaystyle B_{1},\ldots ,B_{k}}$を互いに素な集合とし、それぞれに ${\displaystyle 0\leq d_{i}\leq |B_{i}|\ (0\leq i\leq k)}$ を定めたとき、${\displaystyle 0\leq i\leq k}$ それぞれにおいて ${\displaystyle |I\cap B_{i}|\leq d_{i}}$ を満たす ${\displaystyle 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) において、マッチングの端点となる点集合 ${\displaystyle S\subseteq U}$ を要素とする集合をFとするとき、(U, F) はマトロイドとなる。これを、横断マトロイド (transversal matroid) と呼ぶ。完全2部グラフ ${\displaystyle K_{n,r}}$ の横断マトロイドは、一様マトロイド ${\displaystyle U_{n}^{r}}$ である。
• 点集合を V とするグラフにおいて、点の部分集合を ${\displaystyle 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の一様マトロイド ${\displaystyle U_{n}^{2}}$ はシルベスターマトロイドである。
• pavingマトロイド（英語版） (paving matroid) は、すべてのサーキットの大きさがランクよりも大きいマトロイドである。例えば、一様マトロイド ${\displaystyle U_{n}^{r}}$ のランクはrであり、サーキットの大きさは常に r + 1 であるため、pavingマトロイドである。
• オイラーマトロイド（英語版）(eulerian matroid) は、要素がサーキットによって分割できるようなマトロイドである。例えば、一様マトロイド ${\displaystyle U_{n}^{r}}$ は r + 1 が n を割り切るとき、かつそのときのみオイラーマトロイドである。

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

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

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

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

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

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

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

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

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

${\displaystyle \ 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)を満たす関数 ${\displaystyle \sigma :2^{E}{\to }2^{E}}$ はマトロイドの閉包関数となる。

ここでは、1つ以上のマトロイド（あるいは独立性システム）から新たなマトロイドを構成する方法について説明する。

独立性システム (E, F) に対して、F^* を ${\displaystyle X\cap B=\emptyset }$ となる (E, F) の基 B が存在する ${\displaystyle X\subseteq E}$ の集合とする。このとき、(E, F^*) を (E,F) の双対 (dual) と定義する。

双対には次のような性質がある。

• (E, F^**) = (E,F)
• (E, F) が独立性システムならば、(E, F^*) は独立性システム
• (E, F) はマトロイド ${\displaystyle \iff }$ (E, F^*) はマトロイド^[2]。
• マトロイド (E, F) とその双対 (E, F^*) とし、それぞれのランク関数を r, r^* とすると、r^* は任意の X ⊆ E に対して ${\displaystyle 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) であると呼ぶ。${\displaystyle 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) のランク関数は ${\displaystyle r(X)=\min _{A{\subseteq }X}(|X\setminus {A}|+\sum _{i=1}^{k}r_{i}(A))}$ である^[3]。

組合せ最適化問題の多くは、独立性システム ${\displaystyle (E,F)}$ とコスト関数 ${\displaystyle c:E\to \mathbb {R} }$ に対して、${\displaystyle \sum _{e\in X}c(e)}$ を最大（あるいは最小）にする ${\displaystyle X\in F}$ を求める最適化問題に定式化できる。

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

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

マトロイドにおいては貪欲法で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、クラスカル法はマトロイド上の貪欲法で説明できるが、プリム法やダイクストラ法は異なる。

最良選択貪欲法は、${\displaystyle c(e)}$ の大きい順に ${\displaystyle e\in E}$ を暫定解に追加できるならば追加し追加できない場合は次の要素に移ることを繰り返すアルゴリズムである。つまり、

1. ${\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})}$ となるように ${\displaystyle E=\{e_{1},e_{2},\cdots ,e_{n}\}}$ をソートする。
2. ${\displaystyle E_{ans}\leftarrow \emptyset }$
3. For i = 1 to n : ${\displaystyle E_{ans}\cup \{e_{i}\}\in F}$ ならば ${\displaystyle E_{ans}\leftarrow E_{ans}\cup \{e_{i}\}}$
4. ${\displaystyle E_{ans}}$を解として出力する。

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

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

${\displaystyle q(E,F)\leq {\frac {c(G)}{c(OPT)}}\leq 1}$

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

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

G を最良選択貪欲法で得られる解、${\displaystyle OPT}$ を最適解とする。${\displaystyle E=\{e_{1},\ldots ,e_{n}\}}$ は、${\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})}$ となるようにソート済みであるとし、${\displaystyle E_{j}=\{e_{1},\ldots ,e_{j}\}}$ とする。また、

${\displaystyle d_{j}={\begin{cases}c(e_{n}),&{\mbox{if }}j=n\\c(e_{j})-c(e_{j+1}),&{\mbox{otherwise}}\end{cases}}}$

とし、任意の ${\displaystyle X\subseteq 2^{E}}$ に対して、${\displaystyle X_{j}=X\cap E_{j}}$ と置く。このとき、次の事実が成り立つ。

• 任意の ${\displaystyle X\subseteq 2^{E}}$ において、${\displaystyle c(X)=\sum _{j=1}^{n}|X_{j}|d_{j}}$^{[注 6]}
• 任意の ${\displaystyle 1\leq j\leq n}$ において、${\displaystyle \rho (E_{j})\leq |G_{j}|}$^{[注 7]}
• 任意の ${\displaystyle X\subseteq E}$ において、${\displaystyle r(X)q(E,F)\leq \rho (X)}$^{[注 8]}
• 任意の ${\displaystyle 1\leq j\leq n}$ において、${\displaystyle |OPT_{j}|\leq r(E_{j})}$^{[注 9]}

以上のことから、

${\displaystyle 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) とコスト関数 ${\displaystyle c:E\to \mathbb {R} _{+}}$に対する最小化問題を解く。最悪棄却貪欲法は、都合の悪い e ∈ E を優先して解から除外する。つまり、

1. ${\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})}$ となるように ${\displaystyle E=\{e_{1},e_{2},\cdots ,e_{n}\}}$ をソートする。
2. ${\displaystyle E_{ans}\leftarrow E}$
3. For i = 1 to n : ${\displaystyle E_{ans}\setminus \{e_{i}\}}$ が基を含むならば、${\displaystyle E_{ans}\leftarrow E_{ans}\setminus \{e_{i}\}}$
4. ${\displaystyle E_{ans}}$ を解として出力する。

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

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

${\displaystyle 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)、コスト関数 ${\displaystyle c:E\to \mathbb {Z} _{+}}$、部分集合 S, S' ⊆ E, ε > 0 が

${\displaystyle {\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) をマトロイドに限定するならば多項式時間アルゴリズムは存在する。

ナップサック問題はこのアルゴリズムが知られている珍しい例で、計算時間が ${\displaystyle O(n^{2}\cdot {\frac {1}{\epsilon }})}$^[12][13][14]や ${\displaystyle 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と劣モジュラ関数 ${\displaystyle f:2^{E}\to \mathbb {R} _{+}}$を用いてポリマトロイド (polymatroid) と呼ばれる有界多面体を定義できる。ポリマトロイドとベクトルに対する分離問題は劣モジュラ関数最小化問題に帰着できる。劣モジュラ関数最小化問題は例えばフローネットワークにおける無向グラフの最小カットを求める問題などを一般化している。劣モジュラ関数最小化問題は楕円体法を用いることで多項式時間で解ける^[17]ことが知られて以来、Schrijverのアルゴリズム^[18]等が知られている。

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

• 組合せ最適化
• グラフ理論
• 計算複雑性理論

• ポリマトロイド
• グリードイド
• 劣モジュラ関数

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