Computational complexity of multicommodity flow problems with uniform assignment of flow

This paper describes multicommodity flow problems with a flow assignment constraint. The multicommodity flow problem requires both the set of paths, to which the commodities are assigned, and the volume, of the commodities assigned for each path. However, this paper treats problems where only paths are required. The flow is assigned to the paths uniformly. This problem appears in STR (State- and Time-dependent Routing) which is a kind of dynamic routing scheme in a circuit-switched network. The paper shows that this problem belongs to the class of NP-complete problems and remains NP-complete if the lengths (number of edges) of paths are restricted to be less than or equal to 2 or the number of commodities is fixed, but can be solved in polynomial time if the path lengths are restricted to be less than or equal to 2 and the number of commodities is fixed. [In Japanese.]