Мы рассмотрим задачу поиска паросочетания в регулярных двудольных графах. Обсудим результаты по этой задаче и её применения. Рассмотрим рандомизированный алгоритм поиска последнего с сублинейным временем работы и докажем нижнюю оценку на время работы любого детерминированного алгоритма.