Максимальное соответствие в бипартном графике

Question

Учитывая двусторонний граф $ g= (v_1 \ cup v_2, e) $ и установленный $ V '\в (v_1 \ cup v_2) $ .Какова сложность нахождения максимального сопоставления в $ G $ , который использует только $ x $ вершиныSpaness Class="Математический контейнер"> $ v '$ ?

Answer 1

Установите $ v_i '= v_i \ cap v' $ . Вы можете решить это, найдя максимальное соответствие, используя при большинстве $ K $ вершины из $ v_1 '$ и На большинстве $ xk $ from $ v_2 '$ для всех $ k \ в [0, x] $ . Это в свою очередь может быть найдено с максимальным потоком.

Чтобы найти это максимальное соответствие, мы изменяем обычное сокращение до максимального потока. Пусть $ S $ Будьте источника и $ T $ Раковина. Пусть $ l $ и $ R $ Будьте вспомогательные вершины. Добавьте край из $ S $ на $ l $ с емкостью $ k $ и край от $ R $ на $ t $ с емкостью $ xk $ . Все остальные края будут иметь мощность $ 1 $ . Добавьте преимущество из $ l $ на каждый $ x \ in v_1 '$ , а из $ S $ на каждый $ x \ in v_1 \ setminus v_1 '$ . Добавьте край от каждого $ y \ in v_2 '$ на $ R $ , а из каждого $ y \ in v_2 \ setminus v_2 '$ на $ t $ . Для $ (x, y) \ in e $ добавьте край от $ x $ $ y $ . Теперь максимальный поток дает максимальное соответствие, используя при большинстве $ k $ вершины в $ v_1 '$ и < Spaness Class= «Математический контейнер»> $ XK $ в $ v_2 '$ .

Таким образом, мы можем решить проблему в $ \ mathcal {o} (x \ cdot m) $ где $ m $ - сложность максимального потока. Максимальные проблемы потока очень похожи, поэтому мы можем улучшить это.

Мы можем увеличить или уменьшить емкость любого края на $ 1 $ при сохранении максимального потока в $ \ mathcal { } (| E |) $ . Сначала рассчитайте максимальное сопоставление, используя никаких вершин в $ V '$ . Затем увеличивайте емкость края из $ S $ на $ l $ by $ x $ . Затем на каждом шаге увеличивайте емкость края из $ R $ на $ t $ и уменьшить емкость края из $ s $ на $ l $ при сохранении максимального потока. Вывести наибольшее подходящее. Сложность будет $ \ mathcal {o} (| e | \ sqrt {| v |} + x \ cdot | e |) $ Если мы используем Dinic, чтобы найти начальное двустороннее соответствие.