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.