Traveler Problem

Problem: Longest Simple Path
Input: A weighted graph G, with specified start and end vertices s and t.
Output: What is the most expensive path from s to t that does not visit any vertex more than once?

This problem differs from TSP in two quite unimportant ways.

  • First, it asks for a path instead of a closed tour. This difference isn’t substantial: we get a closed tour by simply including the edge (t, s).
  • Second, it asks for the most expensive path instead of the least expensive tour. Again this difference isn’t very significant: it encourages us to visit as many vertices as possible (ideally all), just as in TSP.
  • The big word in the problem statement is simple, meaning we are not allowed to visit any vertex more than once.

let LP[i, j] as a function denoting the length of the longest simple path from i to j. Note that the longest simple path from i to j had to visit some vertex x right before reaching j. Thus, the last edge visited must be of the form (x, j). This suggests the following recurrence relation to compute the length of the longest path, where c(x, j) is the cost/weight of edge (x, j)

$LP[i, j] = \max\limits_{(x, j) \in E} \ \ LP[i, x] + c(x, j)$

however, above expression does nothing to enforce simplicity. How do we know that vertex j has not appeared previously on the longest simple path from i to x?

Thus LP[i, j, P] denotes the longest simple path from i to j, where P is the exact sequence of intermediate vertices between i and j on this path. The following recurrence relation works to compute
this, where P + x denotes appending x to the end of P:

$LP[i, j, P+x] = \max\limits_{(x, j) \in E, x, j \not\in P} \ \ LP[i, x, P] + c(x, j)$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License