Is Network Flow Pseudo-Polynomial Time?
We Know That Normal Knapsack Problem Has Pseudo-Polynomial Time, Because of the Runtime of O(Nw). I Was Wondering Whether the Runtime of Network Flow Is...
We know that normal knapsack problem has pseudo-polynomial time, because of the runtime of O(nW). I was wondering whether the runtime of network flow is pseudo-polynomial time because the runtime of network flow using Ford-Fulkerson Algorithm is O(Cm)(m for number of edges and C for the sum of capacity of edges leaving from start point)?
1 Answer
Yes, the Ford-Fulkerson algorithm is a pseudopolynomial time algorithm. Its runtime is O(Cm), where C is the sum of the capacities leaving the start node. Since writing out the number C requires O(log C) bits, this runtime is indeed pseudopolynomial but not actually polynomial.
Strongly-polynomial time algorithms do exist for maximum flow, though, such as the push-relabel algorithm, which runs in time O(n3).
Hope this helps!
Marcus Vance is a cybersecurity auditor and technology writer dedicated to educating the public about online safety, data privacy regulations, enterprise security, and emerging cyber threats.
