マトロイドオラクル

数学やコンピュータサイエンスにおいて、マトロイドオラクルとは、アルゴリズムがマトロイドにアクセスするためのサブルーチンであり、マトロイドとは、ベクトル空間内のベクトル間の線形依存関係やグラフの全域木などを記述するために使用できる抽象的な組み合わせ構造である。

この種のオラクルで最も一般的に使用されているのは独立性オラクルであり、マトロイド要素の集合が独立しているかどうかをテストするサブルーチンです。他にもいくつかの種類のオラクルが使用されており、独立性オラクルよりも弱いもの、強いもの、計算能力が同等のものなど様々です。^{[ 1 ]}

マトロイド上で計算を実行する多くのアルゴリズムは、オラクルを入力として受け取るように設計されており、様々な種類のマトロイドに対して変更を加えることなく効率的に実行でき、使用するマトロイドの種類に関する追加の仮定も不要です。例えば、任意のマトロイドの独立性オラクルが与えられれば、独立性オラクルを使用して各要素を追加できるかどうかをテストし、要素を重み順にソートして基底に追加する貪欲アルゴリズムを適用することで、マトロイドの最小重み基底を見つけることができます。^{[ 2 ]}

計算複雑性理論において、オラクルモデルは、 P ≠ NPなどの証明されていない仮定を援用することなく、特定のマトロイド問題を多項式時間で解くことができないことを証明する無条件の下限をもたらしました。このようにして困難であることが示されている問題には、マトロイドがバイナリか一様かをテストすること、または特定の固定マイナーが含まれているかどうかをテストすることなどがあります。^{[ 3 ]}

一部の著者は、マトロイドのすべての独立集合またはすべての基底集合を明示的にリストするマトロイドのコンピュータ表現を試みていますが、^{[ 4 ]}これらの表現は簡潔ではありません。${\displaystyle n}$要素は、指数関数的に空間を占める表現に拡張される可能性がある${\displaystyle n}$実際、${\displaystyle n}$要素は二重指数関数的に増加する

${\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}$^{[ 5 ]}

このことから、考えられるすべてのマトロイドを扱うことができる明示的な表現は、必然的に指数空間を使用することになる。^{[ 6 ]}

その代わりに、さまざまな種類のマトロイドは、それらが定義されている他の構造からより効率的に表現できます。例えば、均一マトロイドは2つの数値パラメータから、グラフマトロイド、二重円マトロイド、ガモイドはグラフから、線形マトロイドは行列から、といった具合です。しかし、任意のマトロイドに対して計算を実行するアルゴリズムは、これらのマトロイドクラスごとに再設計するのではなく、引数にアクセスするための統一的な方法を必要とします。オラクルモデルは、アルゴリズムが必要とするアクセスの種類をコード化して分類する便利な方法を提供します。

ラド（1942）に始まり、「独立関数」または「${\displaystyle I}$「独立関数」は、マトロイドを公理化する多くの同等の方法の1つとして研究されてきた。独立関数は、マトロイド要素の集合を数にマッピングする。${\displaystyle 1}$セットが独立である場合、または${\displaystyle 0}$それが従属的である場合、つまり、それは独立集合の族の指示関数であり、本質的には独立オラクルと同じものである。 ^{[ 7 ]}

マトロイドオラクルは、マトロイドに関する初期のアルゴリズム研究の一部でもありました。例えば、エドモンズ（1965）は、マトロイド分割問題を研究する際に、与えられたマトロイドへのアクセスは、独立した集合を入力として受け取るサブルーチンを介して行われると仮定しました。${\displaystyle I}$そして要素${\displaystyle x}$、そして、回路を返す${\displaystyle I\cup \{x\}}$（必然的にユニークで、${\displaystyle x}$（存在する場合）またはそのような回路が存在しないことを判定します。エドモンズ（1971）は、与えられた集合が独立であるかどうかをテストするサブルーチン（より現代的な用語では、独立性オラクル）を使用し、それが提供する情報で最小重み基底を多項式時間で見つけるのに十分であることを観察しました。

Korte & Hausmann (1978)および Hausmann & Korte (1978)の研究を皮切りに 、研究者たちはマトロイドや関連構造のアルゴリズムの下限を証明するという観点からオラクルの研究を始めた。Hausmann と Korte によるこれら 2 つの論文は、最大カーディナリティ独立集合を見つける問題に関するもので、マトロイドでは容易だが、(彼らが示したように) 独立オラクルによって表現されるより一般的な独立システムでは近似したり正確に計算したりするのが困難である。この研究は、1970 年代後半から 1980 年代初頭にかけて、マトロイドの問題に対する同様の困難性の結果を示す論文^{[ 8 ]や、さまざまな種類のマトロイド オラクルの能力を比較する論文[ 9 ]}が相次ぐきっかけとなった。

それ以来、独立性オラクルはマトロイドアルゴリズムに関するほとんどの研究の標準となっています。^{[ 10 ]}また、下限に関する研究^{[ 11 ]や、異なるタイプのオラクルの比較[ 12 ]}も継続的に行われています。

以下のタイプのマトロイドオラクルが検討されてきた。

• 独立性オラクルは、入力としてマトロイド要素の集合を受け取り、出力としてブール値を返します。与えられた集合が独立であれば真、そうでなければ偽です。^{[ 13 ]}これは、グラフィックマトロイド、横断マトロイド、ガモイド、線形マトロイド、およびこれらから直接和などの標準的な演算によって形成されるマトロイドについて、マトロイドが定義された基盤構造に基づいて容易に実装できます。^{[ 3 ]}
• 基底オラクルは、入力としてマトロイド要素の集合を受け取り、出力としてブール値を返します。与えられた集合が基底であれば真、そうでなければ偽です。^{[ 9 ]}
• 回路オラクルは、入力としてマトロイド要素の集合を受け取り、出力としてブール値を返します。与えられた集合が回路であれば真、そうでなければ偽です。^{[ 9 ]}
• エドモンズ（1965）の回路探索オラクルは、入力として独立集合と追加要素を受け取り、それらの和集合が独立集合であるかどうかを判断するか、和集合の中に回路を見つけてそれを返します。
• ランクオラクルは、入力としてマトロイド要素の集合を受け取り、出力として与えられた集合のランクである数値を返します。 ^{[ 9 ]}
• 3種類の閉包オラクルが検討されてきた。1つ目は、与えられた要素が与えられた集合の閉包に属するかどうかをテストするもの、2つ目は集合の閉包を返すもの、3つ目は与えられた集合が閉包であるかどうかをテストするものである。^{[ 9 ]}
• スパニングオラクルは、入力としてマトロイド要素の集合を受け取り、出力としてブール値を返します。与えられた集合がスパンニング（つまり、基底を含み、マトロイド全体と同じランクを持つ）であればtrue、そうでなければfalseです。^{[ 14 ]}
• 周長オラクルは、入力としてマトロイド要素のセットを受け取り、出力としてそのセット内の最小回路のサイズである数値（または${\displaystyle +\infty }$与えられた集合が独立である場合）。^{[ 14 ]}
• 固定要素用のポートオラクル${\displaystyle x}$マトロイドの関数は、入力としてマトロイド要素のセットを受け取り、出力としてブール値を返します。指定されたセットに、次の要素を含む回路が含まれている場合は、true になります。${\displaystyle x}$そうでなければ偽である。^{[ 15 ]}

オラクルには多くの種類が知られていますが、その多くは計算能力が同等であるため、どれを使用するかの選択は簡略化できます。${\displaystyle X}$別のオラクルに多項式時間で還元できると言われている${\displaystyle Y}$呼び出しがあった場合${\displaystyle X}$マトロイドにオラクルのみを使用してアクセスするアルゴリズムによってシミュレートされる可能性がある${\displaystyle Y}$そして、マトロイドの要素数で測ると多項式時間で実行できます。計算複雑性理論の観点から言えば、これはチューリング還元です。2つのオラクルは、互いに多項式時間で還元できる場合、多項式的に等価であると言われます。${\displaystyle X}$そして${\displaystyle Y}$多項式的に等価である場合、オラクルを使用してマトロイド問題に対する多項式時間アルゴリズムの存在または非存在を証明するすべての結果${\displaystyle X}$Oracleについても同じことが証明される${\displaystyle Y}$。

例えば、独立性オラクルは、エドモンズ（1965）の回路探索オラクルと多項式的に等価である。回路探索オラクルが利用可能な場合、集合の独立性は最大で を用いてテストできる。${\displaystyle n}$空の集合から始めて、与えられた集合の要素を一度に1つずつ追加し、回路探索オラクルを使用して、各追加がこれまでに構築された集合の独立性を維持するかどうかをテストすることによって、オラクルを呼び出します。反対方向には、独立性オラクルが利用可能な場合、集合内の回路が${\displaystyle I\cup \{x\}}$最大で${\displaystyle n}$各要素をテストしてオラクルを呼び出す${\displaystyle y\in I}$、 かどうか${\displaystyle I\setminus \{y\}\cup \{x\}}$は独立しており、答えが「いいえ」である要素を返します。独立性オラクルは、ランクオラクル、スパニングオラクル、最初の 2 種類のクロージャオラクル、およびポートオラクルと多項式的に等価です。^{[ 1 ]}

基底オラクル、回路オラクル、および与えられた集合が閉じているかどうかをテストするオラクルはすべて独立性オラクルよりも弱い。独立性オラクルを使用してマトロイドにアクセスするアルゴリズムによって多項式時間でシミュレートできるが、その逆はできない。さらに、これら 3 つのオラクルはいずれも多項式時間内に互いをシミュレートすることはできない。周長オラクルは、同じ意味で独立性オラクルよりも強い。^{[ 9 ]}

多項式時間チューリング還元に加えて、他のタイプの還元可能性も検討されてきた。特に、Karp、Upfal 、 Wigderson（1988）は、並列アルゴリズムにおいて、ランクオラクルと独立性オラクルは計算能力において大きく異なることを示した。ランクオラクルは、最小重み基底の構築を可能にする。${\displaystyle n}$マトロイド要素のソート順の接頭辞に対する同時クエリ：要素が最適基底に属するのは、その接頭辞のランクが前の接頭辞のランクと異なる場合のみである。対照的に、独立オラクルを使用して最小基底を見つけるのははるかに遅い。決定論的に解くことができるのは${\displaystyle O({\sqrt {n}})}$時間ステップ、そして下限値があります${\displaystyle \Omega ((n/\log n)^{1/3})}$ランダム化並列アルゴリズムの場合でも同様です。

マトロイドに関する多くの問題は、独立性オラクルまたは同等の能力を持つ別のオラクルのみを介してマトロイドにアクセスするアルゴリズムによって、多項式時間で解けることが知られています。これらのアルゴリズムは、与えられたマトロイドの種類に関する追加の仮定を必要としません。多項式時間で解ける問題には、以下のようなものがあります。

• 貪欲アルゴリズムを使用して、重み付きマトロイドの最小または最大の重み基底を見つける。^{[ 2 ]}
• マトロイドの要素を最小限の数の独立集合に分割し、与えられた 2 つのマトロイドで同時に独立である最大の集合を見つける。後者の問題はマトロイド交差と呼ばれ、両方の問題の解は互いに密接に関連している。^{[ 16 ]}
• マトロイドが${\displaystyle k}$-接続されている（ Tutte 1966の意味で）${\displaystyle k\leq 3}$[ ^{17 ]​}
• 与えられたマトロイドがグラフィックであるかどうか^{[ 18 ]}または正則であるかどうかをテストします。^{[ 19 ]}
• 与えられたマトロイドの耳分解とは、和集合がマトロイドであり、かつ、その系列内の前のすべての回路を縮約した後も各回路が回路のままであるような回路のシーケンスのことである。このような分解は、選択されたマトロイド要素がすべての回路に属するという追加の性質を持つ場合もある。^{[ 15 ]}
• 与えられたマトロイドの分岐幅が固定定数以下である場合に、その分岐分解を見つける。 ^{[ 20 ]}
• マトロイドのすべての基底、平面、または回路を、出力セットごとに多項式時間でリストアップします。^{[ 21 ]}
• 完全多項式時間ランダム化近似スキームによる基底数の近似、マトロイドの場合${\displaystyle n}$要素とランク${\displaystyle r}$さらに、基数の数が多項式因子の範囲内であるという仮定を置く。${\displaystyle r}$-要素セット。^{[ 22 ]}

多くのマトロイド問題では、独立性オラクルが問題を多項式時間で解くのに十分な能力を提供しないことを示すことができます。これらの証明の主なアイデアは、2 つのマトロイドを見つけることです。${\displaystyle M}$そして${\displaystyle M'}$問題の答えが異なり、アルゴリズムが区別するのが難しいもの。特に、${\displaystyle M}$対称性が高く、${\displaystyle M'}$少数のクエリに対する回答のみで、アルゴリズムが入力タイプを確実に区別するには、非常に多くのクエリが必要になる場合があります。${\displaystyle M}$対称性のいずれかを使用して形成された入力から${\displaystyle M}$順列にする${\displaystyle M'}$[ ^{3 ]​}

このアプローチの簡単な例として、マトロイドが一様であるかどうかをテストするのが難しいことを示すことができる。説明を簡潔にするため、${\displaystyle n}$均等に、${\displaystyle M}$均一なマトロイドである${\displaystyle U{}_{n}^{n/2}}$、そして${\displaystyle M'}$から形成されたマトロイドである${\displaystyle M}$1つを作ることで${\displaystyle n/2}$-元素基底セット${\displaystyle M}$独立ではなく依存。アルゴリズムが入力が均一かどうかを正しくテストするには、${\displaystyle M}$あらゆる可能な順列から${\displaystyle M'}$しかし、決定論的アルゴリズムがそうするためには、${\displaystyle n/2}$要素のサブセット: 1 つのセットが欠落している場合、同じセットを依存するセットとして選択したオラクルに騙される可能性があります。したがって、マトロイドが一様かどうかをテストするには、

${\displaystyle {\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)}$

独立性クエリは多項式よりもはるかに多い。ランダム化アルゴリズムでさえ、これら2つのマトロイドを区別できると確信するためには、ほぼ同数のクエリを実行する必要がある。^{[ 23 ]}

Jensen & Korte (1982)は、2 つのマトロイドが存在する場合、${\displaystyle M}$そして${\displaystyle M'}$同じ要素セットだが問題の解答が異なる場合、それらの要素で与えられた問題を正しく解くアルゴリズムは少なくとも

${\displaystyle {\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}}$

クエリ、${\displaystyle \operatorname {aut} (M)}$は自己同型群を表す。${\displaystyle M}$、${\displaystyle Q_{i}}$独立性が異なる集合の族を表す。${\displaystyle M}$に${\displaystyle M'}$、 そして${\displaystyle \operatorname {fix} (M,Q_{i})}$は、 を写像する自己同型写像​​のサブグループを表す。${\displaystyle Q_{i}}$自身に。例えば、一様マトロイドの自己同型群は、サイズが の対称群に等しい。${\displaystyle n!}$、一様マトロイドのテスト問題では、セットは1つだけだった。${\displaystyle Q_{i}}$と${\displaystyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}}$指数関数的に小さい${\displaystyle n!}$[ ^{24 ]​}

マトロイドオラクルアルゴリズムでは多項式時間で計算することが不可能であることが証明されている問題には、以下のようなものがある。

• 与えられたマトロイドが一様であるかどうかをテストする。^{[ 23 ]}
• 与えられたマトロイドが固定マトロイドを含むかどうかをテストする${\displaystyle H}$未成年者として、特別な場合を除いて${\displaystyle H}$ランクまたは共ランクが最大で 1 である一様である。より一般的には、$\displaystyle {\mathcal {H}}}$は固定された有限のマトロイドの集合であり、 には一様マトロイドは存在しない。$\displaystyle {\mathcal {H}}}$すると、与えられたマトロイドが の 1 つ以上のマトロイドを含むかどうかを多項式時間でテストすることは不可能になります。$\displaystyle {\mathcal {H}}}$未成年者として。^{[ 25 ]}
• 与えられたマトロイドがバイナリであるかどうか、特定の固定体上で表現可能であるかどうか、または表現可能な体が存在するかどうかをテストします。^{[ 26 ]}
• マトロイドマッチング問題の解決では、入力はグラフとその頂点上のマトロイドであり、目標は、マッチングされた頂点が独立した集合を形成するという制約の下で、可能な限り大きなマッチングをグラフ内で見つけることである。^{[ 27 ]}
• 与えられたマトロイドが自己双対、横断的、二部グラフ、オイラー的、または向き付け可能であるかどうかをテストします。^{[ 3 ]}
• 与えられたマトロイドの周長（最小回路のサイズ）、最大回路のサイズ、回路の数、基底の数、フラットの数、最大ランクのフラットの数、最大のフラットのサイズ、Tutte 多項式、または連結性を計算する。^{[ 3 ]}

すべてのプロパティのセットの中で${\displaystyle n}$要素マトロイドの場合、指数時間でのテストを必要としない特性の割合は、極限においてゼロに近づきます。${\displaystyle n}$無限大に及ぶ。^{[ 6 ]}

• ブラックボックス群、群論におけるオラクルのようなモデル
• 暗黙的グラフ：グラフアルゴリズムのためのオラクル型モデル