Minimum Mean Cycle and the Shape of Negative-Weight Answers

When a graph contains a reachable negative cycle, distances from the source are unbounded below and the algorithms in Bellman-Ford, Round Counts, and Negative-Cycle Detection can report only that the problem has no answer. But “no answer” is rarely the end of the question. A network of currency exchanges with arbitrage, a scheduling graph with a violated constraint set, and a manufacturing process whose throughput is limited by a feedback loop all raise the same issue: the useful quantity is a property of the cycle itself, and the standard property is the smallest total weight divided by the number of edges.

Why the mean rather than the sum

Define the mean weight of a cycle $C$ with $k$ edges as $w(C)/k$, and let

$$\mu^* = \min_{C} \frac{w(C)}{|C|}$$

over all cycles in the graph. If the graph has no cycle at all, $\mu^* = \infty$; if it has a negative cycle, $\mu^* < 0$.

The mean is the right normaliser because it is invariant under the operation that matters: traversing a cycle repeatedly. Walking a cycle $C$ exactly $m$ times gives a closed walk of weight $m \cdot w(C)$ and length $m \cdot |C|$, whose mean is unchanged. So the mean of a cycle is a property of the cycle’s shape, not of how many times it is repeated, and a bound on $\mu^*$ is exactly a statement about the asymptotic per-edge cost of long walks.

That invariance is what makes the quantity useful in practice. A negative cycle of total weight $-1$ over 1,000 edges lowers the distance by only a thousandth per edge, so a shortest-path routine that iterates a bounded number of rounds may fail to notice it before its round budget expires; the distances are wrong but not obviously so. The mean exposes the per-edge rate directly.

The quantity also connects to a different problem entirely. In a max-plus system, a timed event graph in which each edge carries a delay and the steady-state period is the maximum mean cycle delay, the maximum mean cycle is the system’s cycle time. The minimisation and maximisation versions are the same problem with signs flipped, and both are solved by the same machinery.

Karp’s characterisation

Let $d_k(v)$ be the minimum weight of a walk from a fixed source $s$ to $v$ using exactly $k$ edges, with $d_0(s) = 0$ and $d_0(v) = \infty$ otherwise, and $d_k(v) = \infty$ when no such walk exists. These values are computed by $n$ rounds of the Bellman-Ford recurrence, each round being one pass over the edges, so the table costs $O(nm)$ time and $O(n^2)$ space for $n$ vertices and $m$ edges.

Karp’s theorem states that, when every vertex is reachable from $s$,

$$\mu^* = \min_{v} ; \max_{0 \le k \le n-1} \frac{d_n(v) - d_k(v)}{n - k}.$$

The formula is exact, not an approximation, and its shape is worth reading. For a fixed $v$, the numerator compares the best walk of exactly $n$ edges with the best walk of exactly $k$ edges; the difference is the cost of the extra $n-k$ edges, and dividing by that count gives an average per edge. Taking the maximum over $k$ picks the $k$ that makes the extra edges as expensive as possible, and taking the minimum over $v$ picks the vertex whose best $n$-edge walk is cheapest relative to its shorter walks.

The intuition is that a walk of $n$ edges must repeat a vertex, since there are only $n$ vertices. The repeated segment is a cycle, and the $n$-edge walk decomposes into a simple path plus a cycle traversed some number of times. The vertex and the $k$ at which the maximum is attained identify the cycle’s entry point and the length of the simple prefix. A walk that traverses a cycle more than once makes the ratio worse, so the optimum is attained by a walk that traverses its cycle exactly once, and the formula’s minimum over $v$ recovers exactly the mean of that cycle.

INF = float('inf')

def min_cycle_mean(n, edges, source=0):
    """edges: list of (u, v, w). Returns the minimum cycle mean, or INF if acyclic."""
    prev = [INF] * n
    prev[source] = 0
    table = [prev]                       # table[k][v] = best walk of exactly k edges
    for _ in range(n):
        cur = [INF] * n
        for u, v, w in edges:
            if prev[u] + w < cur[v]:
                cur[v] = prev[u] + w
        table.append(cur)
        prev = cur
    best = INF
    for v in range(n):
        if table[n][v] == INF:
            continue                     # v unreachable from source
        worst = -INF
        for k in range(n):
            if table[k][v] == INF:
                continue
            worst = max(worst, (table[n][v] - table[k][v]) / (n - k))
        best = min(best, worst)
    return best

Two details in the code are easy to get wrong. The table must hold exactly $k$ edges, so an entry can be $\infty$ even when the vertex is reachable by a shorter walk; substituting the shorter distance would break the characterisation. And the maximum over $k$ ranges over $0 \le k \le n-1$, not up to $n$; the term $k = n$ has denominator zero.

Parametric search as an alternative

The mean cycle problem can also be reduced to negative-cycle detection. For a candidate value $\lambda$, replace each edge weight $w(u,v)$ with $w(u,v) - \lambda$ and ask whether the graph has a negative cycle. Such a cycle exists exactly when

$$\sum_{(u,v) \in C} \big( w(u,v) - \lambda \big) < 0 \iff \frac{w(C)}{|C|} < \lambda.$$

So the predicate ”$\mu^* < \lambda$” is decided by a single Bellman-Ford run at $O(nm)$, and $\mu^*$ is the threshold of that monotone predicate. Binary search over $\lambda$ converges in a number of iterations set by the precision required, which for integer weights can be made exact by searching over rationals with denominator bounded by $n$, since the mean of a cycle of at most $n$ edges has that denominator.

The method is slower than Karp’s by a logarithmic factor but far more flexible. It extends to constraints that break the characterisation: a minimum mean cycle through a specified vertex, or one restricted to a subset of edges, is not expressible in Karp’s formula but is a straightforward parametric search if the detection step is replaced by a constrained detection step. The trade is the familiar one, a general method with a worse constant against a specialised method with a proof.

A third approach, Howard’s policy iteration, is what large implementations often use. It maintains a current policy, one outgoing edge per vertex, forming a functional graph, finds a cycle in it, evaluates that cycle’s mean, and improves the policy by redirecting vertices whose best alternative edge beats the current policy under the current mean. It has no polynomial worst-case bound but converges quickly in practice on the structured graphs where the problem arises. That combination, no worst-case guarantee and good behaviour on structured instances, is why it is used for cycle-time computation in max-plus models.

Interpreting the answer

The output of the computation is one number, and its interpretation depends on which of three regimes the graph is in.

If $\mu^* > 0$, every cycle has positive weight, the graph has no negative cycle, and shortest paths are well defined. Karp’s formula still returns a value, and the value is a lower bound on the per-edge cost of any cycle.

If $\mu^* = 0$, the graph contains a cycle of total weight zero. Distances are still well defined and finite, because zero-weight cycles do not lower them, but the shortest path is not unique in a strong sense: any path can be padded with a zero cycle at no cost, and implementations that reconstruct paths must decide whether to include such detours. The distinction between $\mu^* = 0$ and $\mu^* > 0$ is invisible to a round-bounded shortest-path routine, which is why the check is worth doing explicitly when weights can be zero or negative.

If $\mu^* < 0$, distances are unbounded below for every vertex reachable from the cycle. The magnitude of $\mu^$ then gives the rate: traversing the cycle $m$ times lowers the distance to its vertices by $m \cdot \mu^$, so after $m$ repetitions the label is below any fixed threshold. For a distance query that must return a finite answer, the only correct responses are to report the cycle or to refuse; for a model whose quantity of interest is a rate, $\mu^*$ is the answer.

Relation to the all-pairs view

The $O(nm)$ cost of Karp’s method is the same order as one Bellman-Ford run, which is cheaper than the all-pairs methods compared in Floyd-Warshall, Johnson Reweighting, and the All-Pairs Choice. That is not a coincidence: the table $d_k(v)$ is the dynamic program over path length, and the all-pairs distance matrix is the fixed point of the same recurrence after the length dimension has been eliminated.

There is a further connection worth noting. In a graph with no negative cycle, the distances from a source satisfy $d[v] \le d[u] + w(u,v)$, and the tight edges, those where equality holds, form the shortest-path tree. The mean cycle value is the obstruction to extending this to a graph with negative cycles: no potential function can satisfy the inequality on every edge when a negative cycle exists, and the minimum mean cycle measures the smallest uniform shift $\lambda$ that would make the shifted weights cycle-nonnegative. That is exactly the parametric formulation above, read as a statement about potentials rather than about cycles.

The cost of the table

Karp’s characterisation requires all vertices to be reachable from the source; unreachable components need either a super-source with zero-weight edges to every vertex or a separate run per component. The $O(n^2)$ table is the binding constraint in practice: for a graph with a hundred thousand vertices it is ten billion entries, which is why the method is used on the small, dense graphs that appear in timing analysis rather than on large sparse networks.

The method also finds the value, not the cycle. Extracting the cycle requires recording the vertex and the $k$ at which the minimum was attained, then walking the corresponding walk’s predecessors, a step that needs a predecessor table of the same size as the distance table and doubles the memory. For the common use case, where only the rate matters, the extraction is unnecessary.