最大基数マッチング

最大濃度マッチングはグラフ理論における基本的な問題である。^[1]グラフ G が与えられ、目標は可能な限り多くの辺を含むマッチングを見つけることである。つまり、各頂点がサブセットの辺の 1 つにしか隣接しないような、辺の最大濃度サブセットを見つけることである。各辺はちょうど 2 つの頂点をカバーするため、この問題は可能な限り多くの頂点をカバーするマッチングを見つけるタスクと同等である。

最大基数マッチング問題の重要な特殊なケースは、 Gが二部グラフであり、その頂点VがXの左頂点とYの右頂点に分割され、Eの辺が常に左頂点と右頂点を接続している場合です。 この場合、一般的な場合よりも単純なアルゴリズムで問題を効率的に解決できます。

最大基数マッチングを計算する最も簡単な方法は、Ford-Fulkerson アルゴリズムに従うことです。このアルゴリズムは、最大フローを計算するというより一般的な問題を解決します。2 部グラフ( X + Y、E )は、次のように フロー ネットワークに変換できます。

• ソース頂点sを追加します。 sからXの各頂点にエッジを追加します。
• シンク頂点tを追加します。Y の各頂点からtへのエッジを追加します。
• 各エッジに容量 1 を割り当てます。

ネットワーク内の各エッジには整数容量があるため、すべてのフローが整数である最大フローが存在します。すべての容量が 1 であるため、これらの整数は 0 または 1 のいずれかでなければなりません。各整数フローは、フローが 1 の場合にのみエッジがマッチングに含まれるマッチングを定義します。これは次の理由でマッチングになります。

• X内の各頂点への入力フローは最大 1 であるため、出力フローも最大 1 であり、したがって、X内の各頂点に隣接するエッジは最大 1 つ存在します。
• Y内の各頂点からの出力フローは最大 1 であるため、入力フローも最大 1 であり、したがって、Y内の各頂点に隣接するエッジは最大 1 つ存在します。

Ford-Fulkerson アルゴリズムは、 x ∈ Xからy ∈ Yへの増加パスを繰り返し見つけ、そのパスとMの対称差を取ってマッチングM を更新することで進行します (そのようなパスが存在すると仮定)。各パスはO ( E )時間で見つけられるため、実行時間はO ( VE )であり、最大マッチングはXからYへのフローを運ぶEのエッジで構成されます。

このアルゴリズムの改良版として、より複雑なホップクロフト-カープ アルゴリズムがあります。このアルゴリズムは、複数の増加パスを同時に検索します。このアルゴリズムは時間内に実行されます。 ${\displaystyle O({\sqrt {V}}E)}$

^{二部グラフに対するChandranとHochbaum [2]}のアルゴリズムは、最大マッチングkの大きさに依存した時間で実行される。これは| X | < | Y |の場合、

${\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).}$

ワードサイズに対するブール演算を使用すると、計算量はさらに^{[2]に改善されます。}${\displaystyle \lambda}$

${\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).}$

特殊な種類の二部グラフには、より効率的なアルゴリズムが存在します。

• 疎な二部グラフの場合、最大マッチング問題は電流フローに基づくマドリのアルゴリズムで解くことができる。^[3]${\displaystyle {\チルダ {O}}(E^{10/7})}$
• 平面二部グラフの場合、複数のソースとシンクを^持つ最大フローの問題に縮小することで、頂点の数をnとすると、 O ( nlog3n )の 時間で問題を解くことができます。 [ ^4]

ブロッサムアルゴリズムは、一般的な（必ずしも二部グラフではない）グラフの最大基数マッチングを見つけます。実行時間は です。一般的なグラフでは、二部グラフでのホップクロフト-カープアルゴリズムのパフォーマンスに匹敵するO ( √ V E )という優れたパフォーマンスが、ミカリとヴァジラニのはるかに複雑なアルゴリズムによって達成できます。^{[5]同じ上限は、ブルーム} [de] ^{[6]のアルゴリズムと}ガボウとタージャンのアルゴリズムによって達成されました。^[7]${\displaystyle O(|V|^{2}\cdot |E|)}$

代替アプローチはランダム化を使用し、高速行列乗算アルゴリズムに基づいています。これにより、複雑度 の一般的なグラフに対してランダム化アルゴリズムが得られます。^{[8]これは、十分に}密なグラフに対しては理論的には優れていますが、実際にはアルゴリズムが遅くなります。^[2]${\displaystyle O(V^{2.372})}$

^{このタスクの他のアルゴリズムは、DuanとPettie [9]}によってレビューされています（表Iを参照）。近似アルゴリズムの観点から、彼らはまた、ブロッサムアルゴリズムとMicaliとVaziraniのアルゴリズムが、任意の固定誤差境界に対して線形時間で実行される 近似アルゴリズムと見なすことができると指摘しています。

• 最大基数マッチングを見つけることで、完全マッチングが存在するかどうかを判断できます。
• 重み付きグラフで最大重みのマッチングを見つける問題は最大重みマッチング問題と呼ばれ、二部グラフへの制限は割り当て問題と呼ばれます。各頂点が一度に複数の頂点にマッチングできる場合、これは一般化された割り当て問題です。
• 優先度マッチングは、優先度の高い頂点が最初にマッチングされる特定の最大カーディナリティ マッチングです。
• ハイパーグラフにおける最大濃度マッチングの問題は、3-ユニフォームハイパーグラフの場合でもNP完全である。^[10]