Maksymalny przepływ

Mamy na wejściu graf skierowany z przepustowościami na krawędziach i ustalonym źródłem i ujściem, chcę znaleźć krawędź o najmniejszej przepustowości, która po zwiększeniu jej przepustowości, zwiększy maksymalny przepływ w grafie wejściowym. Czy widzi ktoś algorytm szybszy niż O(E * max_flow(V, E)), gdzie max_flow(V, E) jest czasem działania maksymalnego przepływu.

Po wymyśleniu nowej metody poprawiam. Chce to zrobić szybciej niż O(n^{4), gdzie n = V jest liczbą wierzchołków. Można to zrobić w czasie O(E}2 + max_flow(V, E)), wystarczy po policzeniu maksymalnego przepływu dla każdej krawędzi zwiększyć jej wartość o 1, zmodyfikować sieć rezydualną i sprawdzić czy ma ścieżkę powiększającą, czas takiego kroku to O(V+E), więc po E krokach to O(E^{2). Gdy zastosujemy zmodyfikowany algorytm push-relabel maksymalnego przepływu o złożoności O(n}3) to dostaniemy czas O(n^4).

OK, wymyśliłem rozwiązanie, które jest bardzo łatwe i działa w O(n^3), wystarczy popatrzyć na min-cuta.