Какая реальная асимптотика Диница на двудольном паросочетании и на сетях с единичными пропускными?
Знаю, что у Диница общая оценка $O(V^2E)$. Но в разборах пишут, что на двудольном паросочетании он работает за $O(E\sqrt{V})$. Откуда берётся $\sqrt{V}$ и какие ещё есть улучшенные оценки для специальных сетей? Хочу понимать, когда Диниц «бесплатно» становится быстрым.
2 ответа
Общая оценка Диница — $O(V^2 E)$ — пессимистична. На специальных сетях она резко улучшается из-за ограничения на число фаз.
1. Единичные пропускные на двудольном паросочетании / сети с единичными capacity: $O(E\sqrt{V})$. Ключ — лемма: после $\sqrt{V}$ фаз остаточный поток (сколько ещё осталось добрать) не превышает $\sqrt{V}$, а каждая оставшаяся единица потока требует не больше одной фазы. Значит фаз всего $O(\sqrt{V})$, каждая $O(E)$ → $O(E\sqrt{V})$. Это в точности оценка Хопкрофта-Карпа для паросочетания.
2. Единичные сети (unit-capacity networks), где у каждой внутренней вершины степень вход/выход = 1: $O(E\sqrt{E})$ или $O(E\sqrt{V})$. Аналогичный аргумент: длина кратчайшего пути растёт, и после $O(\sqrt{E})$ фаз поток почти добран.
3. Планарные сети, сети с малыми целыми capacity — свои улучшенные оценки.
Практический вывод: если в задаче все пропускные = 1 (паросочетания, Менгер, выбор непересекающихся путей), смело считайте Диница как $O(E\sqrt{V})$ — он пройдёт там, где «общий» max-flow по верхней оценке кажется медленным. Память всегда $O(V+E)$.
На произвольных больших пропускных же оценка остаётся $O(V^2E)$, но на практике Диниц почти всегда работает кардинально быстрее теоретической границы — поэтому он де-факто стандарт в CP.
Стоит подчеркнуть: оценка $O(V^2E)$ — это число фаз $\le V$ (т.к. кратчайшее $s\to t$ строго растёт после каждой фазы, а длина не больше $V$), умноженное на стоимость одной фазы $O(VE)$ (блокирующий поток с указателями). На единичных сетях число фаз падает до $\sqrt{\cdot}$, а стоимость фазы — до $O(E)$ (каждое ребро насыщается один раз), отсюда и ускорение. То есть оба множителя улучшаются. Понимание «откуда $V$ и откуда $VE$» помогает на ходу прикинуть, пройдёт ли поток по времени для данных ограничений.