Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

Question

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as minimal average cost cycles, but use Bellman-Ford to discover a minimal cycle and augment along the discovered cycle. Let $V$ be the number of nodes in the graph, $A$ the number of edges, $U$ the maximal capacity of an edge in the graph, and $W$ the maximal costs of an edge in the graph. Then, my learning materials claim:

• The maximal costs at the beginning can be no more than $AUW$
• The augmentation along one negative cycle reduces the costs by at least one unit
• The lower bound for the minimal costs is 0, because we don't allow negative costs
• Each negative cycle can be found in $O(VA)$

And they follow from it that the algorithm's complexity is $O(V^2AUW)$. I understand the logic behind each of the claims, but think that the complexity is different. Specifically, the maximal number of augmentations is given by one unit of flow per augmentation, taking the costs from $AUW$ to zero, giving us a maximum of $AUW$ augmentations. We need to discover a negative cycle for each, so we multiply the maximal number of augmentations by the time needed to discover a cycle ($VA$) and arrive at $O(A^2VUW)$ for the algorithm.

Could this be an error in the learning materials (this is a text provided by the professor, not a student's notes from the course), or is my logic wrong?

Answer 1

You are correct, using the claims found in the book, we can obtain the time complexity by finding that $O(AUW) \times O(VA) = O(A^2VUW)$.

But, a time complexity of $O(V^2AUW)$ could be considered when we look at the SPFA algorithm to find a negative cycle in $O(E) = O(V^2)$ time on average, yielding a time complexity of $O(AUW) \times O(V^2) = O(V^2AUW)$.

Answer 2

According to TopCoder the correct running time is $O( A^2 \cdot VUW)$.