Integer Maximum Flow (Maximum Flow)

Description

Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities must be integers.

Related Problems

Generalizations: Non-Integer Maximum Flow

Subproblem: Unweighted Maximum Flow

Related: st-Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow, Maximum Local Edge Connectivity

Parameters

$V$: number of vertices

$E$: number of edges

$U$: maximum edge capacity

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Ford & Fulkerson	1955	$O(E^{2}U)$	$O(E)$	Exact	Deterministic	Time & Space
Dinitz	1970	$O(V^{2}E)$	$O(E)$	Exact	Deterministic	Time & Space
Edmonds & Karp	1972	$O(E^{2} \log U)$	$O(E)$	Exact	Deterministic	Time & Space
Karzanov	1974	$O(V^{3})$	$O(V^{2})$	Exact	Deterministic	Time & Space
Galil & Naamad	1980	$O(VE \log^{2} V)$	$O(E)$	Exact	Deterministic	Time & Space
Dantzig	1951	$O(V^{2}EU)$	$O(VE)$?	Exact	Deterministic
Dinitz (with dynamic trees)	1973	$O(VE \log U)$	$O(E)$	Exact	Deterministic	Time
Cherkassky	1977	$O(V^{2}E^{0.5})$	$O(E)$	Exact	Deterministic	Time & Space
Sleator & Tarjan	1983	$O(VE \log V)$	$O(E)$	Exact	Deterministic	Time
Goldberg & Tarjan	1986	$O(VE \log (V^{2}/E))$	$O(E)$	Exact	Deterministic	Time
Ahuja & Orlin	1987	$O(VE + V^{2} \log U)$	$O(ELogU)$	Exact	Deterministic	Time
Goldberg & Rao	1997	$O(E^{1.5} \log(V^{2}/E) \log U)$	$O(V + E)$	Exact	Deterministic	Time
Goldberg & Rao	1997	$O(V^{0.{6}6}E \log(V^{2}/E) \log U)$	$O(V + E)$	Exact	Deterministic	Time
Ahuja et al.	1987	$O(VELog(V(LogU)$^{0.5} / E))		Exact	Deterministic	Time
MKM Algorithm	1978	$O(V^{3})$	$O(E)$	Exact	Deterministic	Time & Space
Galil	1978	$O(V^({5}/{3})$E^({2}/{3}))	$O(E)$	Exact	Deterministic	Time & Space
Shiloach	1981	$O(V^{3}*log(V)$/p)	$O(E)$	Exact	Parallel	Time
Gabow	1985	$O(VE*logU)$	$O(E)$	Exact	Deterministic	Time
Lee, Sidford	2014	$O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U))	$O(E)$	Exact	Deterministic	Time
Madry	2016	$O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U))	$O(E)$	Exact	Deterministic	Time
Kathuria, Liu, Sidford	2020	$O(E^({1}+o({1})$)/sqrt(eps))	$O(E)$ or $O(V^{2})$ ?	1+eps	Deterministic	Time
Kathuria, Liu, Sidford	2020	$O(E^({4}/{3}+o({1})$)U^({1}/{3}))	$O(E)$ or $O(V^{2})$ ?	Exact	Deterministic	Time
Brand et al	2021	$O((E+V^{1.5})$log(U)polylog(V, E, log U))	$O(E)$	Exact	Randomized	Time
Gao, Liu, Peng	2021	$O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E))	$O(E)$	Exact	Deterministic	Time
Chen et al	2022	$O(E^({1}+o({1})$)*log(U))	$O(E)$	Exact	Deterministic	Time
Goldberg & Rao (Parallel)	1997	$O(V^{1.66} log(V)$ log(U))	$O(V^{2})$	Exact	Parallel	Time & Space
Goldberg & Rao (Parallel)	1997	$O(E^{0.5} V log(V)$ log(U))	$O(V^{2})$	Exact	Parallel	Time & Space

Time Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination

References/Citation

https://arxiv.org/abs/2203.00671,