Maximum concurrent flow problems and p-modulus

Abstract

Maximum flow problems involve finding a feasible flow of maximum value through a single source-sink flow network. The flow must satisfy the restriction that the amount of flow into any node other than the source and sink node equals the amount of flow out of it. Moreover, the amount of flow across an edge cannot exceed the capacity of that edge.

Maximum multicommodity flow problems are a generalization of maximum flow problems that involve finding an optimal flow between multiple source and sink pairs. The maximum concurrent flow problem is a more complex and popular variation of the maximum multicommodity flow problem, where we are given a set of positive demands and the goal is finding an optimal flow between multiple source-sink pairs.

The p-modulus problem provides a general framework for quantifying the richness of a family of objects on a graph. Recent advances in the theory have led to several new interpretations of modulus. In the case of a single source and sink, it has been shown that the single source-sink maximum flow problem is dual to the 1-modulus problem. Similarly, it is known that 2-modulus is related to effective resistances and p-modulus is related to the shortest path problem.

Inspired by these properties of single source-sink networks, we show that the maximum concurrent flow problem can be embedded into a one-parameter family of p-modulus problems. Using the flexibility provided by the modulus framework, this allows us to introduce a family of generalizations of p-modulus problems. This connection to modulus provides a natural generalization of effective resistance and shortest path to networks with multiple source-sink pairs.