最大1対多マッチング

Question

$ g=（x + y、e）$ は、バイパリットグラフと $ k \ geq 1 $ 整数。 最大 $ K $ - マッチングは、 $ e $ のサブセットです。 $ x $ の各頂点は、 $ k $ エッジと $ Y $ は、 $ 1 $ エッジに隣接しています。

最大カーディナリティ $ k $ - マッチングは、次のアルゴリズムで見つけることができます：

• $ k $ 各コピーがx $ の$ k $ コピーのコピー。 $ x $ のすべての隣接に隣接しています。
• 結果のグラフで最大マッチングを見つけます。

verticesと $ m $ エッジを備えたグラフの実行時の複雑さHopcroft-KARPアルゴリズムを使用することは、 $ O（km \ sqrt {kn}）= O（k ^ {3/2} \ Cdot M \ SQRT {n}）$ 。

次の代替アルゴリズムに興味があります：

• repeat $ k $ 回数：

  • $ g $ で最大マッチングを見つけます。
  • グラフから $ y $ の照合頂点を削除します。

そのランタイムの複雑さは $ O（k \ cdot m \ sqrt {n}）$ です。

しかし、このアルゴリズムは常に最大 $ k $ - マッチング？

Answer 1

いいえ。これはCenterExampleです。 $ x={a、b \}、y={c、d、e、f \}、e={AC、AE、AE、bf \}、k= 2 $ 。アルゴリズムの最初の反復は、 $ \ {ae、bf \} $ （特にエッジ $ AE $ "を選択できます。）は、1つが存在していても解決策が見つからないのを防ぐことができます。 $ \ {AC、AD、BE、BF \} $ 。