Minimum Cost Paths in Periodic Graphs

Abstract

We consider graphs with d-dimensional integral vector weights and rational cost values associated with the edges. We analyze the problem of finding a minimum cost path between two given vertices such that the vector sum of all edges in the path equals a given target vector m. The present paper shows that there are polynomial time algorithms for finding such a minimum cost m-path if the dimension of the vector weights is bounded by a constant and the vector weights are represented unary, where the general version is NP-complete under various restrictions.