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)?
21 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!
3
