The Maximum Flow in a Time-Varying Network

The classical maximum flow problem is to send flow from the source to the sink as much as possible. The problem is static, in that arc capacity is a constant. Max-flow min-cut theorem of Fold and Fulkerson [1] is a fundamental result which reveals the relationship between the maximum flow and the minimum cut in a static network. It has played an important role not only in investigating the classical maximum flow problem, but also in developing graph theory, since many results could be regarded as its corollaries.In practical situations, there are, however, numerous problems where the attributes of the network under consideration are time-varying. In such a network, a flow must take a certain time to traverse an arc. The transit time on an arc and the capacity of an arc are all time-varying parameters. To depart at the best time, a flow can wait at the beginning vertex of an arc, which is however constrained by a time-varying vertex capacity. For instance, consider a network in which several cargo-transportation services are available between a number of cities. These may include air transportation, sea transportation, and road transportation, which are available at different times and have different capacities. Waiting at a city is permitted, but it is limited by the space of the warehouse, and dependent upon the time. A question often asked is: what is the maximum flow that can be sent between two particular cities within a certain duration T?We show that this time-varying maximum flow problem is NP-complete. We then establish the max-flow min-cut theorem in the time-varying version. With this result, we develop an approach, which can solve the time-varying maximum flow problem with arbitrary waiting time at vertices in a pseudopolynomial time.