ABSTRACT A dynamic network is a directed graph where an arc has a capacity and a transit time. A dynamic flow is a flow defined in a dynamic network. We consider the problem of finding a minimum‐cost dynamic flow in a dynamic network where an arc has a cost. It is known that this problem is NP‐hard. Klinz and Woeginger asked whether the minimum‐cost dynamic flow problem in a fixed graph (i.e., a graph is given a priori, and it is not a part of the input) can be solved in polynomial time. We prove that if the cost …