Bipartite Perfect Matchingの存在

Question

$ b = g（l、r、e）$を二倍のグラフとします。このグラフが完璧にマッチしているかどうかを知りたいです。このグラフが完全に一致しているかどうかをテストする1つの方法は、ホールの結婚定理ですが、非効率的です（すなわち$ | mathcal p（l）| = 2^{| l |} $テスト - 多項式ではありません）。最大のカーディナリティマッチングを計算してその完璧さをテストすることで、完璧なマッチングが存在するかどうかを常に確認できますが、これにはその完全なマッチングを計算することが含まれます。

ありますか 効率的 マッチングを計算せずに完璧な二部マッチングが存在するかどうかを決定する方法は？理想的には、Hopcroft KarpやMatrixベースのマッチングアルゴリズムなどのアルゴリズムよりも高速なアルゴリズムが必要です。

編集：イタリック部分。

Answer 1

簡単な文献レビューでは、密度の高い二部グラフが完全に一致しているかどうかを決定するための最速のアルゴリズムは、時間内に実行されるマトリックスアルゴリズムであることを示唆しています。 $ o（| v |^ omega）$. 。アルゴリズムのスペースを減らすことができます。 分離、マッチング、カウント Allender、Reinhardt、Zhou。 最近の論文 平面グラフに焦点を当てた2010年から、Allender et alの結果が示唆されています。知られている最高です。