Is network flow pseudo-polynomial time?

Question

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)?

Answer 1

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(n³).

Hope this helps!