Weakly and Strongly Polynomial Algorithms for Computing the Maximum Decrease in Uniform Arc Capacities

Mehdi Ghiyasvand

In this paper, a new problem on a directed network is presented. Let $D$ be a feasible network such that all arc capacities are equal to $U$. Given a $\tau > 0$, the network $D$ with arc capacities $U - \tau$ is called the $\tau$-network. The goal of the problem is to compute the largest $\tau$ such that the $\tau$-network is feasible. First, we present a weakly polynomial time algorithm to solve this problem, which runs in $O(\log(nU))$ maximum flow computations, where $n$ is the number of nodes. Then, an $O(m^2n)$ time approach is presented, where $m$ is the number of arcs. Both weakly and strongly polynomial algorithms are inspired by McCormick and Ervolina(1994).