# Ford-Fulkerson pseudo-polynomial

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?

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$$.