2

I'm looking for an algorithm that takes a directed, weighted graph (with positive integer weights) and finds the cycle in the graph with the smallest average weight (as opposed to total weight).

Based on similar questions (but for total weight), I considered applying a modification of the Floyd–Warshall algorithm, but it would rely on the following property, which does not hold (thank you Ron Teller for providing a counterexample to show this): "For vertices U,V,W, if there are paths p1,p2 from U to V, and paths p3,p4 from V to W, then the optimal combination of these paths to get from U to W is the better of p1,p2 followed by the better of p3,p4."

What other algorithms might I consider that don't rely on this property?

Edit: Moved the following paragraph, which is no longer relevant, below the question.

While this property seems intuitive, it doesn't seem to hold in the case of two paths that are equally desirable. For example, if p1 has total weight 2 and length 2, and p2 has total weight 3 and length 3, neither one is better than the other. However, if p3 and p4 have greater total weights than lengths, p2 is preferable to p1. In my desired application, weights of each edge are positive integers, so this property is enforced and I think I can assume that, in the case of a tie, longer paths are better. However, I still can't prove that this works, so I can't verify the correctness of any algorithm relying on it.

William Luc Ritchie
  • 1,666
  • 1
  • 11
  • 15

3 Answers3

2

"While this property seems intuitive, it doesn't seem to hold in the case of two paths that are equally desirable."

Actually, when you are considering 2 parameters (weight, length), it doesn't hold in any case, here's an example when P1 that in itself has a smaller average than P2, can be sometimes better (example 1) for the final solution or worse (example 2), depending on P3 and P4.

Example 1:

L(P1) = 9, W(P1) = 10
L(P2) = 1, W(P2) = 1
L(P3) = 1, W(P3) = 1
L(P4) = 1, W(P4) = 1

Example 2:

L(P1) = 9, W(P1) = 10
L(P2) = 1, W(P2) = 1
L(P3) = 5, W(P3) = 10
L(P4) = 5, W(P4) = 10

These two parameters have an effect on your objective function that cannot be determined locally, thus the Floyd–Warshall algorithm with any modification won't work.

Since you are considering cycles only, you might want to consider a brute force algorithm that validates the average weight of each of the cycles in the graph. you can do it in polynomial time, see: Finding all cycles in graph

Community
  • 1
  • 1
Ron Teller
  • 1,880
  • 1
  • 12
  • 23
  • You're absolutely right - however, in my application I can add the constraint that for all P, L(P) >= W(P). With that constraint, does the required property hold (with the restriction that a longer path is more desirable than a shorter path in the case of a tie)? – William Luc Ritchie Oct 18 '13 at 15:58
  • 1
    @wlritchi still no. here's another example: (1) `L[1]=40 W[1]=30 L[2]=4 W[2]=2 L[3]=1 W[3]=1 L[4]=1 W[4]=1` (2) `L[1]=40 W[1]=30 L[2]=4 W[2]=2 L[3]=1 W[3]=1 L[4]=100 W[4]=100`. in example (1) P2 is better and in (2) P1 is better. – Ron Teller Oct 19 '13 at 08:24
1

I can suggest another algorithm.

Let's fix C. Now substract C from all weights. How would the answer change? If we substracted the same number from all weights then the average weight of each cycle decreased on the same number C. Now let's check wether we have cycles with negative average weight. The condition of being of negative average weight is equal to condition of being of negative weight. So it's enough to check wether we have cycle with negative weight. We can do it using Bellman-Ford algorithm. If we have such a cycle then the answer is less than C.

So now we can find the answer via binary search. The resulting complexity wil be O(VE log(MaxWeight))

sbeliakov
  • 2,169
  • 1
  • 20
  • 37
  • I quite like this approach, but it only succeeds in detecting cycles in a graph such that every vertex is reachable from the chosen source. The simplest way to avoid this restriction is to run with each vertex as the source, but that gives complexity O(V^2E log(MaxWeight)). – William Luc Ritchie Oct 18 '13 at 16:23
  • 1
    I think we can avoid this problem by decomposing graph into connected components at the beginning – sbeliakov Oct 18 '13 at 17:41
  • To find these connected components, would it be sufficient to pick a source, take the component consisting of vertices reachable from the source, and repeat with a new source (outside the components found so far) until all vertices have been included in at least one component? – William Luc Ritchie Oct 19 '13 at 05:41
  • 1
    Unfortunatelly no. But instead we can decompose graph into strongly connected components. We can do it with linear time using [Kosaraju's algorithm](http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm) for example. Than work with each component independently. We can do it because if there is a cycle in graph it belongs to one of the components because all cycle's vertices are reachable from each other. – sbeliakov Oct 19 '13 at 16:33
  • Why doesn't my proposed method work (even if it is inefficient)? Any cycle will be included in a component if and only if a vertex in this cycle is reachable from one of the sources chosen so far. Since each vertex will have been included in a component, each cycle will have been included in one (or more) as well. – William Luc Ritchie Oct 19 '13 at 17:09
  • Actually, I don't think decomposing is necessary. Instead, we introduce an artificial source vertex which has a zero-weight edge to each other vertex, and use that. Since no vertex has a path to the artificial source, this has no effect on the minimum mean cycle. Young et al. [provide a different algorithm](http://arxiv.org/pdf/cs/0205041.pdf) that also employs this. – William Luc Ritchie Oct 19 '13 at 17:41
  • Yeah, the idea about extra vertex is great! And sorry about rejecting first idea. It seems to work. Strongly connected components are not necessary. – sbeliakov Oct 19 '13 at 20:01
0

The problem you describe is called the minimum mean cycle problem and can be solved efficiently. Further, there's some really nice optimization theory to check out if you're interested (start with the standard reference AMO93).

Mikael Call
  • 75
  • 1
  • 8