Max-Balancing Weighted Directed Graphs and Matrix Scaling

Abstract

A weighted directed graph G is a triple (V, A, g) where (V, A) is a directed graph and g is an arbitrary real-valued function defined on the arc set A. Let G be a strongly-connected, simple weighted directed graph. We say that G is max-balanced if for every nontrivial subset of the vertices W, the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. We show that there exists a (up to an additive constant) unique potential p_v for v ∈ V such that (V, A, g^p) is max-balanced where g_a^p = p_u + g_a − p_v for a = (u, v) ∈ A. We describe an O(|V|²|A|) algorithm for computing p using an algorithm for computing the maximum cycle-mean of G. Finally, we apply our principal result to the similarity scaling of nonnegative matrices.