Karp Minimum Mean Cycle

Find the lightest average-weight directed cycle through a dynamic-programming certificate.

Karp Minimum Mean Cycle

Karp's algorithm identifies the minimum cycle mean of a directed, strongly connected graph. By maintaining a dynamic programming table of shortest walk distances of exact lengths, we can determine the cycle with the smallest average edge weight, which can also detect negative cycles.

Worked Example

Consider the Unit triangle graph with Edge offset 0. The edges are:
(0→1, w=1), (1→2, w=1), (2→0, w=1).

We compute the shortest walk of exactly k edges to each vertex v, with d0(v) = 0 for ALL vertices.

Initialization (k=0):
d0(0) = 0, d0(1) = 0, d0(2) = 0

Iteration 1 (k=1):
d1(0) = d0(2) + 1 = 1
d1(1) = d0(0) + 1 = 1
d1(2) = d0(1) + 1 = 1

Iteration 2 (k=2):
d2(0) = d1(2) + 1 = 2
d2(1) = d1(0) + 1 = 2
d2(2) = d1(1) + 1 = 2

Iteration 3 (k=3):
d3(0) = d2(2) + 1 = 3
d3(1) = d2(0) + 1 = 3
d3(2) = d2(1) + 1 = 3

To find the minimum mean cycle, for each vertex we compute:
max_{0<=k<3}(d3(v)-dk(v))/(3-k)

For v=1:
k=0: (3 - 0)/3 = 1
k=1: (3 - 1)/2 = 1
k=2: (3 - 2)/1 = 1
Max for v=1 is 1.

Since the graph is symmetric, the max for v=0 and v=2 is also 1.
The overall minimum cycle mean is 1.

Interactive Experiment

You can interactively explore the algorithm on different graphs using the module here. Follow these steps:

Select the Graph "Mixed" to see a more complex structure with varied weights.
Set the Edge offset to "0" initially.
Set the Vertex to "1" to focus on the bounds computed for vertex 1.
Set the Walk length to "3" to observe the full prefix walk cost. Note the DP costs and the "Minimum cycle mean".
Change the Edge offset to "-1". The minimum cycle mean will shift exactly by the offset, confirming the uniformity property.

Limitations

Karp's algorithm relies on the graph being finite and strongly connected (or requires a dedicated source vertex connected to all others with weight 0). It identifies the minimum average weight of a cycle, which is distinct from the absolute shortest path length between two vertices. If the graph contains a negative cycle, this algorithm will find a negative minimum mean cycle, but it does not report the standard shortest-path distance from a chosen root.

References

These external primary sources provide the complete theoretical foundation and dynamic programming proof for the minimum mean cycle algorithm.

Karp, R. M. (1977). A characterization of the minimum cycle mean in a digraph.- Berkeley Technical Report introducing the algorithm.
Karp, R. M. (1978). A characterization of the minimum cycle mean in a digraph.- The published paper detailing the dynamic programming approach.

Karp Minimum Mean Cycle