Graphs With Variable Edge Costs.

Consider a graph with a range of costs associated with each vertex and each edge of the graph. The range of costs for a given edge represents the possible costs charged for traversing the edge. The range of costs for a vertex defines the allowable costs to reach that vertex. We study paths in such graphs where the cost of each edge of the path must be chosen within the range of costs for that edge and the sum of the chosen costs of the edges from the start of the path to any vertex in the path must belong to the range of allowable costs for that vertex. In particular, it is shown that for a fixed sequence of vertices, a linear time algorithm solves the problem of choosing the edge costs to satisfy the vertex cost constraints along the path defined by the sequence of vertices. However, deciding if such a path exists from a given vertex to another specified vertex (without specifying the intermediate vertices on the path) is NP-complete. The problem of finding a tour of the vertices satisfying the cost constraints is shown to be NP-complete. The study of these graphs is motivated by problems concerned with the routing of a robot vehicle with upper and lower speed limits.