О потоках в простых двунаправленных и кососимметрических сетях

Пусть задана простая направленная сеть. Результаты Карзанова, Эвена и Таржана показывают, что метод блокирующего потока позволяет построить в ней максимальный целочисленный поток за время $O(m\min(m^{1/2},n^{2/3}))$ (здесь и далее $n$ – число вершин, $m$ – число дуг).
Если данная сеть является простой двунаправленной, то сведение, предложенное Габовым, позволяет решать задачу о максимальном целочисленном потоке в ней за время $O(m^{3/2})$. В статье показано, что эта задача разрешима также и за время $O(mn^{2/3})$ с помощью варианта метода блокирующего потока, тем самым полностью ликвидирован зазор между сложностями направленного и двунаправленного вариантов.
Результаты изложены в эквивалентных терминах кососимметрических сетей. Для получения требуемой оценки $O(mn^{2/3})$ доказывается, что величина целочисленного $s$–$s'$ потока в кососимметрической сети без кратных дуг не превосходит $O(Un^2/d^2)$, где $d$ – длина кратчайшего регулярного $s$–$s'$ пути в расщепленной сети, a $U$ – максимальная пропускная способность. Мы также устанавливаем, что если поток величины $v$ в кососимметрической сети без кратных дуг является ациклическим, то он принимает ненулевые значения лишь на $O(n\sqrt v)$ дугах.