Ford-Fulkerson pseudo-polynomial

Question

Can somebody explain please why Ford-Fulkerson Algorithm has pseudo-polynomial complexity? I understand that the complexity in this case strongly depends on the capacities of the edges of the network, since we have $O(|E|*f_{max})$, but why is the algorithm still not polynomial?

Answer 1

Lets recall that input for flow problems is a graph with capacities on their edges. Let $G(V,E)$ where $V$ denotes the vertex set of the graph and $E$ denotes the edge set. Let $f_{\text{max}}$ denote the maximum possible flow. It is an easy caluclation that input size is $\mathcal{O}(V+E \log (f_{\text{max}}))$ bits as writing $f_{\text{max}}$ takes $\mathcal{O}(\log f_{\text{max}})$ bits. Since $f_{\text{max}}$ may be arbitrarily high (it depends neither on $V$ or $E$), this running time could be arbitrarily high, as a function of $V$ and $E$.

A algorithm is said to have a polynomial runnning time if its runtime in input size in bits where as pseudo-polynomial runtime means runtime of the algorithm is polynomial in numeric value of the input (see Pseudo-polynomial time)