Reverse maximum flow problem under the Chebyshev distance

Given a network 𝐺(𝑉,𝐴,𝑢) with two specific nodes, a source node 𝑠 and a sink node 𝑡, the reverse maximum flow problem is to increase the capacity of some arcs (𝑖,𝑗) as little as possible so that the maximum flow value from 𝑠 to 𝑡 in the modified network is lower bounded by a prescribed value 𝑣0. In this paper, we study the reverse maximum flow problem under the Chebyshev distance and present an efficient algorithm to solve the problem.