The Exact Path Length Problem

✍ Scribed by Matti Nykänen; Esko Ukkonen

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 126 KB
• Volume: 42
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1201

✦ Synopsis

We study a problem related to finding shortest paths in weighted graphs. We ask whether or not there is a path between two nodes that has a given total cost k. The edge weights of the graph can be both positive and negative integers or even integer vectors. We show that many variants of this problem are NP-complete. We develop a pseudo-polynomial algorithm for (both positive and negative) integer weights. The running time of this algorithm is O W 2 n 3 + k min k W n 2 , where n is the number of nodes in the graph, W is the largest absolute value of any edge weight, and k is the target cost. The algorithm is based on preprocessing the graph with a relaxation algorithm to eliminate the effects of weight sign alternations along a path. This preprocessing stage is applicable to other problems as well. For example, we show how to find the minimum absolute cost of any path between two given nodes in a graph with integer weights in O W 2 n 3 time.