Substitutes and complements in network flows viewed as discrete convexity

We study combinatorial properties of the optimal value function of the network flow problem. It is shown by Gale–Politof Substitutes and complements in networks flow problems, Discrete Appl. Math. 3 (1981) 175–186] that the optimal value function has submodularity and supermodularity w.r.t. problem parameters such as weights and capacities. In this paper we shed a new light on this result from the viewpoint of discrete convex analysis to point out that the submodularity and supermodularity are naturally implied by discrete convexity, called M-convexity and L-convexity, of the optimal value function.