Karp's Minimum Mean Cycle Algorithm, in depth: the formula, why it works, cycle extraction and faster alternatives

The problem, and its link to negative cycles

Let the graph have n vertices and m edges with real weights, possibly negative. For a cycle C with k edges, its mean is w(C)/k. Write mu* for the minimum over all cycles. If the graph has no cycle the problem has no answer, and the algorithm must report that.

Two observations make the problem tractable. First, subtracting a constant t from every edge weight subtracts t from every cycle mean, so mu* is exactly the value of t at which the reweighted graph has no negative cycle but has a zero-weight cycle. That links the problem to negative cycle detection, and it immediately gives a slow algorithm: binary search on t, running Bellman-Ford at each guess. Second, under the reweighting by mu*, shortest paths are well defined, every cycle weighs zero or more, and the optimal cycles weigh exactly zero. Karp's proof uses the second observation without ever doing the binary search.

The table and the formula

Define D_k(v) as the minimum weight of a walk with exactly k edges that ends at v, starting anywhere. Starting anywhere is the same as adding a virtual source with zero-weight edges to every vertex, and it means the algorithm works even when the graph is not strongly connected. The table fills row by row, in the same style as the Bellman-Ford recurrences described in dynamic programming:

D_0(v) = 0                                    for every v
D_k(v) = min over edges (u, v) of D_{k-1}(u) + w(u, v)     (infinity if no such walk)

Karp's theorem states that the minimum cycle mean is

mu* = min over v with D_n(v) finite of  max over 0 <= k <= n-1 with D_k(v) finite of  (D_n(v) - D_k(v)) / (n - k)

Read it inside out. For a fixed v and k, the fraction compares the best n-edge walk to v with the best k-edge walk to v, and divides by the n - k extra edges. A walk with n edges visits n + 1 vertices, so it must repeat one and contains a cycle. The fraction estimates the mean of the cycles those extra edges contain. The max over k picks the most pessimistic estimate for v, and the min over v picks the best vertex.

Why the formula is right

The proof is short once you reweight. Because the formula is unchanged by subtracting mu* from every edge (each D_k(v) drops by k times mu*, so each fraction drops by exactly mu*), it is enough to prove that the formula equals zero when mu* = 0.

Every term is at least zero for some k. With mu* = 0 there are no negative cycles, so the shortest walk to v of any length is attained by a simple path, of length less than n. Call its weight pi(v) = min over k < n of D_k(v). The n-edge walk to v is a path plus cycles, each weighing at least zero, so D_n(v) >= pi(v). Choosing k to be the length of that shortest path gives a non-negative fraction, so the max over k is at least zero for every v.

Some vertex reaches exactly zero. Take a zero-weight cycle C and a vertex x on it. Follow a shortest path to x, of j < n edges, then keep walking around C for n - j more edges, stopping at some vertex v. Going round C from x to v and from v back to x adds up to zero, and each part is at least the difference in pi, so pi(v) equals pi(x) plus the weight of the stretch of C from x to v. The walk just built has exactly that weight, so D_n(v) = pi(v). Every D_k(v) is at least pi(v), so every fraction for this v is at most zero, and the max is exactly zero. Hence the min over v is zero.

Implementation with exact arithmetic and cycle extraction

The implementation below uses Fraction so the final comparison is exact, keeps parent pointers so the cycle can be recovered, and verifies the cycle it returns.

from fractions import Fraction

def min_mean_cycle(n, edges):
    # edges: list of (u, v, w) with 0 <= u, v < n and integer w
    INF = None
    D = [[INF] * n for _ in range(n + 1)]
    P = [[None] * n for _ in range(n + 1)]
    D[0] = [0] * n                                   # virtual source
    for k in range(1, n + 1):
        prev, cur, par = D[k - 1], D[k], P[k]
        for u, v, w in edges:
            if prev[u] is not None and (cur[v] is None or prev[u] + w < cur[v]):
                cur[v], par[v] = prev[u] + w, u
    best, arg = None, None
    for v in range(n):
        if D[n][v] is None:
            continue
        worst = max(Fraction(D[n][v] - D[k][v], n - k)
                    for k in range(n) if D[k][v] is not None)
        if best is None or worst < best:
            best, arg = worst, v
    if best is None:
        return None, []                              # acyclic graph
    walk, v = [arg], arg                             # walk back n edges from arg
    for k in range(n, 0, -1):
        v = P[k][v]
        walk.append(v)
    walk.reverse()
    seen = {}
    for i, x in enumerate(walk):                     # first repeated vertex closes a cycle
        if x in seen:
            cycle = walk[seen[x]:i]
            break
        seen[x] = i
    weight = {}
    for u, v, w in edges:
        weight[(u, v)] = min(w, weight.get((u, v), w))
    total = sum(weight[(cycle[i], cycle[(i + 1) % len(cycle)])] for i in range(len(cycle)))
    assert Fraction(total, len(cycle)) == best, "fall back to tight-edge search"
    return best, cycle

Cycle extraction deserves care. The n-edge walk ending at the minimising vertex must contain a cycle, and the standard argument says cycles on it are optimal. In a check of 3,000 random small graphs against brute-force enumeration, the first cycle on that walk always had mean mu*. That is evidence, not proof, so the code asserts it. If the assert ever fires, use the fallback: subtract mu* from every weight, compute shortest distances with Bellman-Ford (no negative cycles now exist), keep only tight edges where d(u) + w - mu* = d(v), and find any cycle in that subgraph with three-colour DFS. Every cycle of tight edges has mean exactly mu*.

Worked example: five vertices, two competing cycles

Take five vertices and eight edges: 0 to 1 weight 4, 1 to 2 weight 1, 2 to 0 weight 1, 1 to 3 weight 2, 3 to 4 weight -1, 4 to 1 weight 2, 2 to 3 weight 5 and 0 to 3 weight 6. By enumeration the simple cycles are 0-1-2 (weight 6, mean 2), 1-3-4 (weight 3, mean 1), 1-2-3-4 (weight 7, mean 7/4) and 0-3-4-1-2 (weight 9, mean 9/5). The answer should be 1.

Row by row, with n = 5:

Check one entry: D_1(4) = -1 because the only edge into 4 is from 3 with weight -1. D_2(1) = 1 because the best two-edge walk into 1 is 3 to 4 to 1, weight -1 + 2.

Now the formula for vertex 1, with D_5(1) = 4: k = 0 gives (4 - 0)/5 = 4/5; k = 1 gives (4 - 2)/4 = 1/2; k = 2 gives (4 - 1)/3 = 1; k = 3 gives (4 - 3)/2 = 1/2; k = 4 gives (4 - 5)/1 = -1. The max is 1. Doing the same for the other vertices gives maxima of 2 for vertices 0, 2, 3 and 4. The minimum over vertices is 1, at vertex 1, matching the enumeration.

Following parent pointers back five edges from vertex 1 gives the walk 3, 4, 1, 3, 4, 1. Its weight is -1 + 2 + 2 - 1 + 2 = 4, which equals D_5(1). The first repeated vertex closes the cycle 3, 4, 1, with mean 1: the red cycle in the figure.

Cost, and faster alternatives

Filling the table costs n passes over m edges, so time is Theta(nm), and the table holds (n + 1) times n entries, so memory is Theta(n squared). Unlike Bellman-Ford there is no early exit: the formula needs all n rows. For a graph with 100,000 vertices the table alone is 10 billion entries, which is why large instances use one of these refinements.

• Two passes, linear memory. Compute only D_n in a first pass, keeping one previous row. In a second pass, recompute rows 0 to n - 1 and update a running max per vertex. Time doubles and memory falls to Theta(n). Walking parent pointers back needs every row, so extract the cycle with the tight-edge fallback instead: Bellman-Ford on weights minus mu*, also in linear space.
• Per strongly connected component. Every cycle lies inside one SCC, so split the graph with Kosaraju's algorithm and run Karp on each component with its own n. Many sparse graphs collapse into small components, which cuts both n and the table size.
• Howard's policy iteration. Each vertex picks one outgoing edge, the resulting functional graph's cycles are evaluated, and policies improve until stable. No good worst-case bound is known, but experimental comparisons such as Dasdan's 2004 study found it among the fastest in practice, often by orders of magnitude over Karp.
• Parametric search. Binary search on t with a negative cycle test. Easy to write, slow and sensitive to precision with real weights, but it generalises to the minimum cycle ratio problem, where each edge has a cost and a time and you minimise total cost over total time.

Where minimum and maximum mean cycles appear

The maximum mean cycle is the same problem with weights negated. In a synchronous circuit or a dataflow graph where edge weights are delays and each cycle carries one token, the maximum cycle mean is the minimum achievable period: no schedule can run faster than its slowest loop. In min-cost circulation, the Goldberg-Tarjan method repeatedly cancels a minimum mean cycle in the residual graph and is strongly polynomial because of that choice; Edmonds-Karp plays the analogous shortest-augmenting-path role for maximum flow. In max-plus algebra the maximum cycle mean is the eigenvalue of the matrix, which describes the long-run growth rate of a periodic system.

Implementation pitfalls

• Floating-point comparison. The final min and max compare fractions that may be equal in exact arithmetic. With integer weights use exact fractions or cross-multiply; with real weights, compare with a tolerance and verify the extracted cycle.
• Infinite entries. Skip k where D_k(v) is infinite and skip v where D_n(v) is infinite. Treating infinity as a large number silently produces a wrong maximum.
• Self-loops and parallel edges. A self-loop is a cycle of length one and is handled naturally. For parallel edges keep the minimum weight when verifying.
• Acyclic input. If every D_n(v) is infinite there is no cycle; return that explicitly rather than a sentinel mean.
• Wrong n after SCC splitting. Use each component's own vertex count in the formula, not the global one.

What to do next

1. Implement the version above and test it against brute-force cycle enumeration on random graphs of up to seven vertices.
2. Reproduce the worked example table by hand for one column before trusting your code.
3. Add SCC decomposition and the two-pass linear-memory variant, and measure both on your real graph sizes.
4. If performance matters, implement Howard's policy iteration and compare it against Karp on your data.
5. Try the reductions: negate weights for maximum mean, and parametric search for cost-over-time ratios.
6. Review SPFA and negative cycle detection, the subroutines behind the fallback and the parametric method.