The access-control problem on capacitated first in first out networks with unique origin–destination paths is hard

This paper is concerned with the performance of multicommodity capacitated networks in a deterministic but time-dependent environment. For a given time-dependent origin–destination table, this paper asks if it is easy to find a way of regulating the input flows into the network to avoid queues from growing internally, i.e., to avoid capacity violations. Problems of this type are conventionally approached in the traffic/transportation field with variational methods such as control theory (if time is continuous) and with mathematical programming (if time is discrete). However, these approaches can only be expected to work well if the set of feasible solutions is convex. Unfortunately, it is found in this paper that this is not the case. It is shown that continuous-time versions of the problem satisfying the smoothness conditions of control theory can have a finite but very large number of feasible solutions. The same happens for the discrete-time case. These difficulties arise even with the simplest versions of the problem (with unique origin–destination paths, perfect information, and deterministic travel times). The paper also shows that the continuous-time feasibility problem is NP-hard, and that if we restrict our attention to (practical) problems whose data can be described with a finite number of bits (e.g., in discrete time), then the problem is NP-complete. These results are established by showing that the problem instances of interest can be related to the Directed Hamiltonian Path problem by a polynomial transformation.