两分的存在完美匹配

Question

令$ b = g（l，r，e）$为两部分图。我想找出这张图是否具有完美的匹配。测试此图是否具有完美匹配的一种方法是Hall的婚姻定理，但效率低下（即$ | Mathcal p（l）| = 2^{| l |} $ tests-不是多项式）。我总是可以通过计算最大的基数匹配并测试其完美度来确定是否存在完美的匹配，但这涉及计算完美匹配。

有吗 高效的 决定是否存在不计算匹配自我的完美二分匹配的方式？理想情况下，我想要一种比Hopcroft KARP或基于矩阵的匹配算法等算法更快的算法，该算法明确地发现了匹配（即，因此不计算匹配是有意义的）。

编辑：斜体部分。

Answer 1

快速文献综述表明，确定密集的两部分图是否具有完美匹配的最快算法仍然是矩阵算法，该算法及时运行 $ O（| V |^ Omega）$. 。您可以减少算法的空间，请参阅 隔离，匹配和计数 由Allender，Reinhardt和Zhou。 最近的论文 从2010年开始，重点是平面图，这表明Allender等人的结果。是已知的最好的。