Finding a "positive cycle"

Question

Suppose we E is an nxn matrix where E[i,j] represents the exchange rate from currency i to currency j. (How much of currency j can be obtained with 1 of currency i). (Note, E[i,j]*E[j,i] is not necessarily 1).

Come up with an algorithm to find a positive cycle if one exists, where a positive cycle is defined by: if you start with 1 of currency i, you can keep exchanging currency such that eventually you can come back and have more than 1 of currency i.

---

I've been thinking about this problem for a long time, but I can't seem to get it. The only thing I can come up with is to represent everything as a directed graph with matrix E as an adjacency matrix, where log(E[i,j]) is the weight between vertices i and j. And then you would look for a cycle with a negative path or something. Does that even make sense? Is there a more efficient/easier way to think of this problem?

Answer 1

First, take logs of exchange rates (this is not strictly necessary, but it means we can talk about "adding lengths" as usual). Then you can apply a slight modification of the Floyd-Warshall algorithm to find the length of a possibly non-simple path (i.e. a path that may loop back on itself several times, and in different places) between every pair of vertices that is at least as long as the longest simple path between them. The only change needed is to flip the sign of the comparison, so that we always look for the longest path (more details below). Finally you can look through all O(n^2) pairs of vertices u and v, taking the sum of the lengths of the 2 paths in each direction (from u to v, and from v to u). If any of these are > 0 then you have found a (possibly non-simple) cycle having overall exchange rate > 1. Overall the FW part of the algorithm dominates, making this O(n^3)-time.

In general, the problem with trying to use an algorithm like FW to find maximum-weight paths is that it might join together 2 subpaths that share one or more vertices, and we usually don't want this. (This can't ever happen when looking for minimum-length paths in a graph with no negative cycles, since such a path would necessarily contain a positive-weight cycle that could be removed, so it would never be chosen as optimal.) This would be a problem if we were looking for the maximum-weight simple cycle; in that case, to get around this we would need to consider a separate subproblem for every subset of vertices, which pushes the time and space complexity up to O(2^n). Fortunately, however, we are only concerned with finding some positive-weight cycle, and it's reasonably easy to see that if the path found by FW happens to use some vertex more than once, then it must contain a nonnegative-weight cycle -- which can either be removed (if it has weight 0), or (if it has weight > 0) is itself a "right answer"!

If you care about finding a simple cycle, this is easy to do in a final step that is linear in the length of the path reported by FW (which, by the way, may be O(2^|V|) -- if all paths have positive length then all "optimal" lengths will double with each outermost iteration -- but that's pretty unlikely to happen here). Take the optimal path pair implied by the result of FW (each path can be calculated in the usual way, by keeping a table of "optimal predecessor" values of k for each vertex pair (i, j)), and simply walk along it, assigning to each vertex you visit the running total of the length so far, until you hit a vertex that you have already visited. At this point, either currentTotal - totalAtAlreadyVisitedVertex > 0, in which case the cycle you just found has positive weight and you're finished, or this difference is 0, in which case you can delete the edges corresponding to this cycle from the path and continue as usual.