Ford-Fulkerson Pseudo-Polinomial

Question

Alguém pode explicar por favor por que o algoritmo Ford-Fulkerson tem complexidade pseudo-polinômio?Eu entendo que a complexidade neste caso depende fortemente das capacidades das bordas da rede, já que temos $ o (| e | * f_ {max}) $ , Mas por que o algoritmo ainda não é polinômio?

Answer 1

permite lembrar que a entrada para problemas de fluxo é um gráfico com capacidades em suas bordas. Deixe $ g (v, e) $ onde $ v $ indica o conjunto de vértices do gráfico e < Span Class="Recipiente de Matemática"> $ E $ Denota o conjunto de borda. Deixe $ f _ {\ text {max}} $ denotam o fluxo máximo possível. É uma calutação fácil que o tamanho da entrada é $ \ mathcal {o} (v + e \ log (f _ {\ text {max}})) $ bits como escrita $ f _ {\ text {max}} $ leva $ \ mathcal {o} (\ log f _ {\ text {max }}) $ bits. Como $ f _ {\ text {max}} $ pode ser arbitrariamente alto (não depende nem na $ v $ ou $ e $ ), este tempo de execução pode ser arbitrariamente alto, como uma função da $ v $ e $ e $ .

Um algoritmo é dito que tenha um tempo de running polinomial se seu tempo de execução no tamanho da entrada em bits onde como tempo de execução pseudo-poliNomial significa tempo de execução do algoritmo é polinômio em valor numérico da entrada (consulte tempo pseudo-polinomial )