Разбиение идеальных соответствий в двудольном графе

Question

В «проблеме брака» мы имеем N мальчиков и N девочек и двоичную матрицу NxN, сообщающую нам, какие пары подходят, и хотим связать каждую девочку с мальчиком. (то есть мы хотим найти идеальное соответствие в двудольном графе).

Теорема Холла гласит, что вы можете найти идеальное соответствие, если каждая коллекция мальчиков-узлов коллективно смежна хотя бы с таким количеством девочек-узлов; и существуют быстрые алгоритмы увеличения пути, которые находят идеальное соответствие.

Я ищу эффективный способ найти наборы мальчиков-узлов, которые в совокупности соседствуют с точно столько же девочек-узлов (то есть у нас есть равенство в критерии Холла). Эти мальчики должны быть в паре с этими девочками, а остальные мальчики - с остальными девочками, чтобы все идеальные соответствия соответствовали этому разделению.

Моя теория графов немного устарела, наверняка должен быть лучший способ, чем перечислять все 2 ^ N подмножества и считать соседей каждого?

Answer 1

Это возможно за полиномиальное время. Смоделируйте вашу задачу согласования двудольных как задачу максимального потока в ориентированном графе. Затем используйте алгоритм для перечисления минимальных сокращений. Поищите в Google слово «перечислить минимальные сокращения» или статьи Вазирани и Яннакакиса или Йе и Вана.

Answer 2

Если я понимаю, что вы хотите, то, увы, нет умного способа сделать это за полиномиальное время. Поиск таких разбиений на общем графе является NP-полной задачей.