Существование двухпартийного идеального сопоставления

Question

Пусть $ b = g (l, r, e) $ будет двудольным графом. Я хочу выяснить, имеет ли этот график идеальное соответствие. Одним из способов проверить, имеет ли этот график идеальное сопоставление, является теорема брака Холла, но он неэффективен (то есть $ | mathcal p (l) | = 2^{| l |} $ tests - не полиномиальные). Я всегда могу выяснить, существует ли идеальное сопоставление, вычислив максимальное соответствие кардинальности и тестирование ее совершенства, но это включает в себя вычисление этого идеального сопоставления.

Есть эффективный Способ решить, существует ли идеальное двухпартное сопоставление без вычисления совпадения самого себя? В идеале я бы хотел алгоритм, который быстрее, чем алгоритмы, такие как Algorithms, такие как Hopcroft KARP или матричные алгоритмы, которые явно обнаруживают сопоставление (то есть, поэтому не вычисление сопоставления имеет смысл).

РЕДАКТИРОВАТЬ: курсивная часть.

Answer 1

Быстрый обзор литературы предполагает, что самый быстрый алгоритм для принятия решения о том, имеет ли плотный двухпартийный график идеальным сопоставлением по -прежнему - алгоритм матрицы, который со временем работает $ O (| v |^ omega) $. Анкет Вы можете уменьшить пространство алгоритма, увидеть Изоляция, сопоставление и подсчет Аллендер, Рейнхардт и Чжоу. Недавняя статья С 2010 года, который фокусируется на плоских графиках, предполагает, что результат Allender et al. это лучшее, что известно.