Задача поиска совершенного паросочетания в регулярном двудольном графе — классическая задача с приложеними к реберной раскраске, маршрутизации и задачам планирования, также связанная с задачей построения разложения Биркгофа-фон Неймана бистохастических матриц. В результате ряда улучшений в 2001 г. для этой задачи был получен алгоритм с линейным временем работы.

В первой части доклада будет рассмотрена задача поиска совершенного паросочетания в регулярных двудольных графах за сублинейное время. Мы покажем, что использование вероятностных методов позволяет получить неожиданно эффективные алгоритмы для этой задачи. С другой стороны, мы покажем, что любому детерминированному алгоритму требуется как минимум линейное время.

В второй части доклада будет рассмотрена следующая коммуникационная задача: Алиса знает граф \( G_A=(P, Q, E_A) \) , Боб знает граф \( G_B=(P, Q, E_B) \), где \( |P|=|Q|=n \). Алиса может послать Бобу сообщение \( m \), зависящее только от \( G_A \), после чего Боб должен выдать паросочетание \( M\subseteq E_A\cup E_B \). Минимальный размер сообщения, которое позволяет Бобу достичь \( 1-\e \) приближения максимального паросочетания в \( G_A\cup G_B \) — это коммуникационная сложность приближения паросочетания с одним раундом, которая также дает нижнюю оценку на однопроходную потоковую сложность приближения максимального паросочетания.

В данной работе исследуется качество приближения, которое можно достичь при помощи сообщения (или памяти) размера \( \tilde O(n) \). Ранее для обеих задач было известно только приближение с коеффициентом \( 1/2 \).

Мы опишем коммуникационный протокол со сложностью \( \tilde O(n) \), при помощи которого достигается приближение с коэффициентом \( 2/3 \), а также покажем, что существенно лучшее приближение имеет сложность \( n^{1+\Omega(1/\log\log n)} \).

Данный коммуникационный протокол также позволяет получить детерминированный однопроходный потоковый алгоритм с памятью \( O(n) \), дающий приближение \( 1-1/e \) для случая, когда вершины на одной стороне графа появляются в потоке вместе со всеми инцидентными ребрами.

Совместная работа с Ашишем Гоэлем и Сандживом Канна.