3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.