ホップクロフト・カープアルゴリズム

ホップクロフト・カープアルゴリズム

クラス	グラフアルゴリズム
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle O(E{\sqrt {V}})}$
最悪の場合の 空間複雑度	${\displaystyle O(V)}$

コンピュータサイエンスにおいて、ホップクロフト・カープアルゴリズム（より正確にはホップクロフト・カープ・カルザノフアルゴリズムと呼ばれることもある）^[1]は、2部グラフを入力として受け取り、最大濃度マッチング（2つの辺が終点を共有しないという特性を持つ、可能な限り多くの辺の集合）を出力するアルゴリズムである。最悪の場合でもで実行され、ここで はグラフの辺の集合、はグラフの頂点の集合であり、 と仮定される。密なグラフの場合、時間制限は となり、疎なランダムグラフの場合は高い確率でで実行される。^[2]${\displaystyle O(|E|{\sqrt {|V|}})}$${\displaystyle E}$${\displaystyle V}$${\displaystyle |E|=\オメガ (|V|)}$${\displaystyle O(|V|^{2.5})}$${\displaystyle O(|E|\log |V|)}$

このアルゴリズムは、ジョン・ホップクロフトとリチャード・カープ （1973年）によって発見され、アレクサンダー・カルザノフ （1973年）によっても独立に発見されました。^[3]ハンガリーアルゴリズムやエドモンズ（1965年）の研究などの以前のマッチング方法と同様に、ホップクロフト–カープアルゴリズムは、増加パスを見つけることによって部分マッチングのサイズを繰り返し増加させます。これらのパスはグラフのエッジのシーケンスであり、マッチング内のエッジと部分マッチング外のエッジが交互に現れ、最初と最後のエッジは部分マッチング内にありません。増加パスを見つけると、増加パスのエッジを切り替えるだけで（部分マッチングに含まれていなかったエッジを部分マッチングに追加し、その逆）、部分マッチングのサイズを増やすことができます。フォード・ファルカーソンアルゴリズムのような、二部マッチングのより単純なアルゴリズムは、反復ごとに1つの増加パスを見つけます。ホップクロフト・カープアルゴリズムは、代わりに、反復ではなく反復のみが必要であることを保証するように、最短の増加パスの最大セットを見つけます。ミカリとヴァジラニのより複雑なアルゴリズムを使用すると、任意のグラフで最大カーディナリティマッチングを見つけるのと同じパフォーマンスを実現できます。^[4]${\displaystyle O({\sqrt {|V|}})}$${\displaystyle O(|V|)}$${\displaystyle O(|E|{\sqrt {|V|}})}$

ホップクロフト・カープアルゴリズムは、最大フロー問題に対するディニックアルゴリズムの特殊なケースとして見ることができる。^[5]

部分的なマッチングにおいてエッジの終点ではない頂点は、自由頂点と呼ばれます。アルゴリズムが依存する基本概念は、拡張パスの概念です。拡張パスは、自由頂点で始まり、自由頂点で終わり、パス内で一致しないエッジと一致するエッジが交互に現れるパスです。この定義から、終点を除き、拡張パス内の他のすべての頂点 (存在する場合) は非自由頂点である必要があります。拡張パスは、2 つの頂点 (両方とも自由) と、それらの間の 1 つの一致しないエッジのみで構成できます。 ${\displaystyle M}$

がマッチングであり、 がに対する増加パスである場合、2 つのエッジ セットの対称差は、サイズ のマッチングを形成します。したがって、増加パスを見つけることにより、アルゴリズムはマッチングのサイズを増やすことができます。 ${\displaystyle M}$${\displaystyle P}$${\displaystyle M}$${\displaystyle M\oplus P}$${\displaystyle |M|+1}$

逆に、マッチングが最適でなく、対称差をとし、 が最適マッチングであるとします。と は両方ともマッチングなので、 におけるすべての頂点の次数は最大で 2 です。したがって、 は、互いに素なサイクル、 における一致する辺と一致しない辺の数が等しいパス、 の増大パス、 の増大パスのコレクションを形成する必要がありますが、 は最適であるため、後者は不可能です。ここで、サイクル、および一致する頂点と一致しない辺の数が等しいパスは、とのサイズの差には影響しないため、この差はにおけるの増大パスの数に等しくなります。したがって、現在のマッチング よりも大きいマッチングが存在する場合は常に、増大パスも存在するはずです。増大パスが見つからない場合は、この場合はが最適である ため、アルゴリズムは安全に終了する可能性があります。${\displaystyle M}$${\displaystyle P}$${\displaystyle M\oplus M^{*}}$${\displaystyle M^{*}}$${\displaystyle M}$${\displaystyle M^{*}}$${\displaystyle P}$${\displaystyle P}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M^{*}}$${\displaystyle M^{*}}$${\displaystyle M}$${\displaystyle M^{*}}$${\displaystyle M}$${\displaystyle P}$${\displaystyle M^{*}}$${\displaystyle M}$${\displaystyle M}$

マッチング問題における増加パスは、最大フロー問題で生じる増加パスと密接に関連しており、この増加パスは、フローの端末間のフロー量を増加させる可能性のあるパスです。 2部マッチング問題を最大フローインスタンスに変換して、マッチング問題の交互パスをフロー問題の増加パスにすることができます。これには、ソースとシンクの2つの頂点を挿入し、ソースから の各頂点へ、および の各頂点からシンクへ単位容量のエッジを挿入し、 から へのエッジが単位容量を持つようにします。[ ^6]任意のネットワークで最大フローを見つけるためにホップクロフト–カープアルゴリズムで使用される手法の一般化は、ディニックのアルゴリズムとして知られています。 ${\displaystyle U}$${\displaystyle V}$${\displaystyle U}$${\displaystyle V}$

このアルゴリズムは次の疑似コードで表現できます。

入力: 二部グラフ${\displaystyle G(U\cup V,E)}$

出力: マッチング${\displaystyle M\subseteq E}$

${\displaystyle M\leftarrow \emptyset }$

繰り返す

${\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}$ 頂点が互いに素な最短増加経路の最大集合

${\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}$

それまで ${\displaystyle {\mathcal {P}}=\emptyset }$

より詳しくは、の二分割における 2 つの集合を と とし、任意の時点での から へのマッチングを集合 として表すものとします。アルゴリズムは段階的に実行されます。各段階は次の手順で構成されます。 ${\displaystyle U}$${\displaystyle V}$${\displaystyle G}$${\displaystyle U}$${\displaystyle V}$${\displaystyle M}$

• 幅優先探索は、グラフの頂点を層に分割します。 の空き頂点はこの探索の開始頂点として使用され、分割の最初の層を形成します。 の空き頂点は定義によりどの一致するエッジにも隣接しないため、探索の最初のレベルでは、一致しないエッジのみがあります。 探索のそれ以降のレベルでは、走査されるエッジは一致するエッジと一致しないエッジを交互に走査する必要があります。つまり、 の頂点から後続の頂点を検索する場合、一致しないエッジのみを走査できますが、 の頂点からは一致するエッジのみを走査できます。の 1 つ以上の空き頂点に到達した最初の層で探索は終了します。${\displaystyle U}$${\displaystyle U}$${\displaystyle U}$${\displaystyle V}$${\displaystyle k}$${\displaystyle V}$
• レイヤー内のすべての自由頂点は、セット に集められます。つまり、頂点は、最短増加パスを終了する場合にのみに配置されます。${\displaystyle V}$${\displaystyle k}$${\displaystyle F}$${\displaystyle v}$${\displaystyle F}$
• アルゴリズムは、長さ の頂点互いに素な増加パスの最大セットを見つけます。(最大とは、これ以上そのようなパスを追加できないことを意味します。これは、より困難なそのようなパスの最大数を見つけることとは異なります。幸い、ここではパスの最大セットを見つければ十分です。) このセットは、から 内の空き頂点への深さ優先探索(DFS)によって計算され、幅優先階層化を使用して探索が行われます。DFS は、前のレイヤーの未使用の頂点につながるエッジのみをたどることができ、DFS ツリー内のパスは、一致するエッジと一致しないエッジの間で交互になる必要があります。 内の頂点の 1 つを含む増加パスが見つかると、DFS は次の開始頂点から続行されます。 DFS 中に遭遇した頂点は、すぐに使用済みとしてマークできます。これは、DFS の現在のポイントでその頂点から へのパスがない場合、その頂点を使用して DFS の他のポイントに到達できないためです。これにより、DFS の実行時間が保証されます。また、 の空き頂点から の空き頂点へという逆方向に作業することも可能です。これは、疑似コードで使用されているバリエーションです。${\displaystyle k}$${\displaystyle F}$${\displaystyle U}$${\displaystyle F}$${\displaystyle U}$${\displaystyle U}$${\displaystyle O(|E|)}$${\displaystyle U}$${\displaystyle V}$
• このようにして見つかったパスはすべて拡大するために使用されます。${\displaystyle M}$

いずれかのフェーズの幅優先探索部分で拡張パスが見つからなくなると、アルゴリズムは終了します。

各フェーズは、1 つの幅優先探索と 1 つの深さ優先探索で構成されます。したがって、1 つのフェーズは で実装できます。したがって、頂点と辺を持つグラフの最初のフェーズには、時間がかかります。 ${\displaystyle O(|E|)}$${\displaystyle {\sqrt {|V|}}}$${\displaystyle |V|}$${\displaystyle |E|}$${\displaystyle O(|E|{\sqrt {|V|}})}$

各フェーズでは、最短増加パスの長さが少なくとも 1 増加します。フェーズでは、指定された長さの増加パスの最大セットが検索されるため、残りの増加パスは必ずこれより長くなります。したがって、アルゴリズムの初期フェーズが完了すると、残りの最短増加パスには少なくとも 個のエッジが含まれます。ただし、最終的な最適マッチングと初期フェーズで見つかった部分マッチングMの対称差は、頂点が互いに素な増加パスと交互サイクルのコレクションを形成します。このコレクション内の各パスの長さが少なくとも である場合、コレクションには最大 個のパスが含まれる可能性があり、最適マッチングのサイズは のサイズと最大個のエッジだけ異なる可能性があります。アルゴリズムの各フェーズではマッチングのサイズが少なくとも 1 増加するため、アルゴリズムが終了する前に最大 個の追加フェーズが存在する可能性があります。 ${\displaystyle {\sqrt {|V|}}}$${\displaystyle {\sqrt {|V|}}}$${\displaystyle {\sqrt {|V|}}}$${\displaystyle {\sqrt {|V|}}}$${\displaystyle M}$${\displaystyle {\sqrt {|V|}}}$${\displaystyle {\sqrt {|V|}}}$

アルゴリズムは最大で合計でフェーズを実行するため、最悪の場合、 合計で時間がかかります。${\displaystyle 2{\sqrt {|V|}}}$${\displaystyle O(|E|{\sqrt {|V|}})}$

ただし、多くの場合、アルゴリズムにかかる時間は、この最悪のケースの分析が示すよりもさらに短くなる可能性があります。たとえば、疎な二部ランダム グラフの平均的なケースでは、Bast ら (2006) (Motwani 1994 の以前の結果を改善) は、すべての非最適マッチングが対数長の増加パスを持つ確率が高いことを示しました。結果として、これらのグラフでは、Hopcroft–Karp アルゴリズムはフェーズと合計時間がかかります。 ${\displaystyle O(\log |V|)}$${\displaystyle O(|E|\log |V|)}$

疎グラフの場合、ホップクロフト-カープアルゴリズムは、引き続き最悪ケースのパフォーマンスが最も優れていることが知られていますが、密グラフ ( ) の場合、Alt ら (1991) による最近のアルゴリズムでは、わずかに優れた時間制限 が達成されています。彼らのアルゴリズムは、プッシュ再ラベル最大フローアルゴリズムを使用し、このアルゴリズムによって作成されたマッチングが最適に近づくと、ホップクロフト-カープ法に切り替えることに基づいています。 ${\displaystyle |E|=\Omega (|V|^{2})}$${\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}$

数人の研究者が二部マッチングアルゴリズムの実験的比較を行っています。その結果は、ホップクロフト-カープ法は理論ほど実用的ではないことを示しています。ホップクロフト-カープ法は、拡張パスを見つけるためのより単純な幅優先および深さ優先戦略や、プッシュ再ラベル技術よりも優れています。^[7]

最短増加経路の最大集合を見つけるという同じアイデアは、非二部グラフで最大濃度マッチングを見つける場合にも機能し、同じ理由で、このアイデアに基づくアルゴリズムはフェーズをとります。ただし、非二部グラフの場合、各フェーズ内で増加経路を見つける作業はより困難です。Micali と Vazirani (1980) は、いくつかのより遅い先駆者たちの研究を基に、線形時間でフェーズを実装する方法を示し、二部グラフの Hopcroft-Karp アルゴリズムと同じ時間制限を持つ非二部マッチング アルゴリズムを生み出しました。Micali-Vazirani の手法は複雑で、その著者たちは結果の完全な証明を提供しませんでした。その後、Peterson と Loui (1988) によって「明確な説明」が発表され、他の著者によって代替方法が説明されました。^[8] 2012 年に、Vazirani は Micali-Vazirani アルゴリズムの新しい簡略化された証明を提供しました。^[9]${\displaystyle O({\sqrt {|V|}})}$

/*
 G = U ∪ V ∪ {NIL}
 ここで、UとVは二部グラフの左側と右側であり、NILは特別なヌル頂点である。
*/
  
関数BFS()は
    U内の各uに対して、 Pair_U[u] = NILの場合に
        
            分布[u] := 0
            エンキュー(Q, u)
        それ以外
            分布[u] := ∞
    分布[NIL] := ∞
    Empty(Q) = falseの場合
        u := デキュー(Q)
        Dist[u] < Dist[NIL]の場合、
             Adj[u]の各vに対して、 Dist[Pair_V[v]] = ∞の場合、
                
                    分布[ペアV[v]] := 分布[u] + 1
                    エンキュー(Q, Pair_V[v])
    Dist[NIL] ≠ ∞を返す

関数DFS(u)は
    、 u ≠ NILの場合、
         Adj[u]の各vに対して、 Dist[Pair_V[v]] = Dist[u] + 1の場合、 DFS(Pair_V[v]) = trueの場合、
            
                
                    ペア_V[v] := u
                    ペア_U[u] := v
                    真を返す
        分布[u] := ∞
        偽を
    返す真を返す

関数ホップクロフト・カープは
    U内の各uに対して
        ペア_U[u] := NIL
    V内の各vに対して
        ペア_V[v] := NIL
    一致:= 0
    BFS() = trueの場合、U
        内の各uに対してPair_U[u] = NILの場合、 DFS(u) = trueの場合、
            
                
                    マッチング := マッチング + 1
    リターンマッチング

グラフの頂点を U と V に分割し、Pair_U テーブルと Pair_V テーブルで示される部分一致について考えます。これらのテーブルには、U と V の各頂点が一致する 1 つの頂点、または一致しない頂点の場合は NIL が含まれます。重要なアイデアは、グラフの両側にダミー頂点を 2 つ追加することです。uDummy は U のすべての一致しない頂点に接続され、vDummy は V のすべての一致しない頂点に接続されます。ここで、 uDummy から vDummy に幅優先探索(BFS) を実行すると、U の現在一致しない頂点を V の現在一致しない頂点に接続する最短の長さのパスを取得できます。グラフは二部グラフであるため、これらのパスは常に U の頂点と V の頂点の間で交互になり、BFS では V から U に移動するときに常に一致するエッジを選択する必要があることに注意してください。 V の一致しない頂点に到達した場合、vDummy で終了し、BFS のパスの検索は終了します。要約すると、BFS は U の一致しない頂点から開始し、V のすべての隣接頂点に進みます。すべてが一致している場合は、これらすべての頂点が一致する (かつ、以前に訪問されていない) U の頂点に戻り、次にこれらの頂点のすべての隣接頂点に進みます。これを、V で到達した頂点の 1 つが一致しなくなるまで繰り返します。

特に、BFS は U の一致しないノードを距離 0 でマークし、U に戻るたびに距離を増分することに注意してください。これにより、BFS で考慮されるパスが、現在マッチングの一部であるエッジで常に V から U に戻りながら、U の一致しない頂点を V の一致しない頂点に接続するための最小限の長さであることが保証されます。特に、vDummy に対応する特別な NIL 頂点には有限の距離が割り当てられるため、BFS 関数は、何らかのパスが見つかった場合にのみ true を返します。パスが見つからない場合は、増加パスは残っておらず、マッチングは最大です。

BFS が true を返す場合、U から V までの最短パス上の頂点のペアリングを更新できます。これは、深さ優先探索(DFS) を使用して行います。最後の頂点を除き、そのようなパス上の V の各頂点は現在一致していることに注意してください。したがって、DFS を使用して探索し、たどるパスが BFS で計算された距離に対応していることを確認できます。現在マッチングしているパスのすべてのエッジをマッチングから削除し、現在マッチングしていないパスのすべてのエッジをマッチングに追加することで、そのようなパスすべてを更新します。これは拡張パスであるため (パスの最初と最後のエッジはマッチングの一部ではなく、パスは一致するエッジと一致しないエッジの間で交互に繰り返される)、これによりマッチングのエッジの数が増加します。これは、現在のマッチングを、現在のマッチングとパス全体の対称差で置き換えることと同じです。

コードにより、考慮するすべての増加パスが頂点分離であることが保証されることに注意してください。実際、パスの対称差を実行した後、そのパスの頂点はいずれも DFS で再度考慮されることはありません。これは、Dist[Pair_V[v]] が Dist[u] + 1 と等しくならないためです (正確には Dist[u] になります)。

また、DFS が同じ頂点を複数回訪問しないことにも注目してください。これは次の行のおかげです。

分布[u] = ∞
偽を返す

頂点 u からの最短増加パスが見つからなかった場合は、DFS は Dist[u] を無限大に設定して頂点 u をマークし、これらの頂点が再度訪問されないようにします。

最後にもう 1 つ注意すべき点は、実際には uDummy は必要ないということです。その役割は、BFS を開始するときに、U の一致しない頂点をすべてキューに入れることです。vDummy については、上記の疑似コードでは NIL として示されています。

• 最大濃度マッチング、アルゴリズムによって解決される問題、および非二部グラフへの一般化
• 割り当て問題、重み付きグラフ上のこの問題の一般化、例えばハンガリーアルゴリズムによって解決される
• 最大フローを求めるエドモンズ・カープアルゴリズム、ホップクロフト・カープアルゴリズムの一般化