Ford-Fulkerson har kjøretid $O(E|f^*|)$, der $|f^*|$ er maks flyt. Dette fordi man potensielt kan øke flyten $E$ ganger. Samme logikk for Edmonds-Karp. Potensielt kan flyten øke $E$ ganger, men hvorfor $O(VE^2)$? Om den bruker BFS, så har vel den kjøretid $O(V+E)$, som totalt gir $O(VE+E^2)$?
Basert på Piazza-spørsmål fra 2015

Hohoi, ja, godt spørsmål. En litt utfordrende analyse, dette. For det første er jeg ikke helt enig med den første analysen din: Man kan øke flyten (i heltallsinkrementer) ganger, og hver iterasjon har en kjøretid på . Så med mindre jeg har misforstått hva du mener, så har du byttet om på de to komponentene i Ford-Fulkerson-kjøretidsanalysen. (Og merk at det bare gjelder hvis du har heltallskapasiteter.)

Forskjellen er altså at i stedet for iterasjoner, kan Edmonds-Karp garantere at vi maksimalt bruker iterasjoner. Men hvorfor?

Lemma 26.7: Den korteste veien i residualnettverket fra til enhver node bortsett fra og øker eller beholder samme verdi i hver iterasjon.

Bevisskisse: Anta at avstanden til synker i en iterasjon. La oss også anta at om dette gjelder flere noder, så har vi valgt den som ligger nærmest etter iterasjonen. La oss si den korteste veien til i residualnettverket etter iterasjonen ender med kanten , som betyr at ligger ett skritt nærmere . Siden vi valgte som den noden nærmest som fikk sin avstand redusert, så kan ikke ha fått sin avstand redusert.

Dersom kanten eksisterte i residualnettverket før denne iterasjonen, så kunne ikke ha hatt en høyere avstand da. Siden vi antok at den fikk sin avstand redusert, kan ikke ha eksistert da – den må ha dukket opp i løpet av denne iterasjonen. Den eneste måten det kan ha skjedd på er at flyten må a økt fra til .

Og det kunne jo potensielt ha skjedd om vi brukte en vilkårlig traverseringsalgoritme, som i Ford-Fulkerson generelt. Men: Edmonds-Karp velger alltid den korteste forøkende sti (med BFS), så om den økte flyten fra til så må den ha fulgt den korteste veien fra til , og den siste kanten i den stien må ha vært .

Den korteste veien til før iterasjonen var én mindre enn den korteste til . Og samtidig vet vi at den korteste veien til etter iterasjonen er én mindre enn den korteste veien til etter iterasjonen. Og vi vet at avstanden til ikke sank. Den eneste konklusjonen er at den korteste veien til før iterasjonen var minst 2 mindre enn den korteste veien til etter iterasjonen. Men vi antok jo at den sank! Vi har altså en selvmotsigelse – det er umulig at noen av de korteste avstandene kan synke. (Men det gjelder altså bare fordi vi fant den korteste forøkende stien.)

I Theorem 26.8 bruker de dette resultatet til å vise at en kant kan være en flaskehals for en forøkende sti maks ganger. Om den skal ha den til å være en flaskehals igjen etter at den nettopp har vært det må du først ha en forøkende sti som går motsatt vei, for å øke flyten fra til , og så tilbake fra til . Du kan jo se ulikheten på side 729, men – long story short – innen kanten er flaskehals neste gang, vil den korteste veien til ha økt med 2. Og det kan jo skje maks ganger. I verste tilfelle kan hver kant være flaskehals helt alene i hver iterasjon. Det kan altså skje for hver av de kantene, som betyr at vi en flaskehals kan oppstå maksimalt ganger. Det vil si, vi har maksimalt iterasjoner.

Oooog siden hver iterasjon tar tid, så blir den totale kjøretiden . Phew!

Boka sier også at maksimal bipartitt matching er . Hvordan er dette raskere, hvis det løses ved å gjøre om til maks flyt og deretter løses? Er det en annen Ford-Fulkerson som brukes, og ikke Edmonds-Karp?

Kjøretiden er både og , dvs., begge er gyldige øvre grenser. I dette tilfellet kan ikke flyten bli større enn , så du kan bytte ut med i den asymptotiske kjøretiden. Faktisk så betyr det at det ikke er noe poeng i å bruke Edmonds-Karp; du kan like gjerne bare kjøre Ford-Fulkerson med DFS, for eksempel, om du vil det.