June 01, 2026
The theory of submodular flows, introduced by Edmonds and Giles, is a cornerstone of combinatorial optimization, unifying network flows, matroid intersections and directed cut coverings. In this paper, we establish a measurable-space version of this framework, addressing the structural existence and duality questions raised as part of Problem 10.6 by Lovász in [1].
We develop a theory of submodular flows on standard Borel spaces and establish the measurable analogues of the existence and optimality theorems. Furthermore, we introduce a measurable notion of the residual graph and characterize extreme flows by combining a base-polytope intersection condition with an acyclicity condition for the measurable residual graph, generalizing the discrete geometric intuition to the infinite-dimensional setting. Finally, we apply the theory to constrained supply-demand problems on measurable bipartite graphs and to fractional measurable orientations.
Flow problems form one of the central paradigms of combinatorial optimization. In a finite directed graph, classical results such as Hoffman’s Circulation Theorem [2] and the Max-Flow-Min-Cut Theorem [3] characterize the existence of feasible circulations and flows under lower and upper capacity constraints. A far-reaching extension of this framework was the submodular flow problem introduced by Edmonds and Giles [4]: Instead of prescribing only edge capacities, the boundary of the flow on every vertex set is controlled by a submodular set function. If \(G=(V,E)\) is a finite digraph and \(f\colon E\to \mathbb{R}\) is a flow, then for a subset \(X\subseteq V\) one writes \(\partial f(X)\) for the net outflow of \(X\); a submodular flow is then a feasible flow \(f\) satisfying \[\partial f(X)\le \varphi(X)\] for all \(X\subseteq V\), where \(\varphi\colon 2^V\to \mathbb{R}\) is a submodular function. This point of view unifies ordinary network flows, cut covering problems, and several polymatroidal constructions, and leads to powerful min-max theorems and polyhedral duality; see, for example, [5], [6].
A different direction, initiated by Lovász [7], extends flow theory from finite graphs to measures on the square of a measurable space \(J\). In that setting, a flow is a finite signed measure on \(J\times J\), a circulation is a measure with equal marginals, and lower and upper capacities are given by bounding measures. Working on standard Borel spaces, Lovász established measurable analogues of Hoffman’s theorem, the supply-demand theorem, and the basic optimality criterion for circulations with cost. Independently, in his study of submodular set functions on general set algebras, Lovász asked whether a corresponding theory of submodular flows exists in the measurable setting [1], which is the main purpose of this paper.
Following [7], we occasionally use the phrase “measurable space” informally, but unless explicitly stated otherwise all spaces in this paper are standard Borel spaces. Our basic object is the following. Let \((J,\mathcal{B})\) be a standard Borel space, let \(\alpha,\beta\in \mathcal{M}(\mathcal{B}^2)\) with \(\alpha\le \beta\), and let \(\varphi\colon \mathcal{B}\to \mathbb{R}\) be a bounded continuous submodular set function with \(\varphi(\emptyset)=\varphi(J)=0\). For a flow \(\mu\in \mathcal{M}(\mathcal{B}^2)\), its boundary is defined as \[\partial\mu(X):=\mu(X\times X^c)-\mu(X^c\times X),\qquad X\in\mathcal{B}.\] We call \(\mu\) a feasible submodular flow for \((J,\mathcal{B},\alpha,\beta,\varphi)\) if \(\alpha\le \mu\le \beta\) and \(\partial\mu\le \varphi\) on \(\mathcal{B}\).
Our first main result is a measurable analogue of the Edmonds-Giles feasibility theorem [4]. We prove in 5 that a feasible submodular flow exists if and only if \[\alpha(X\times X^c)-\beta(X^c\times X)\le \varphi(X)\] for all \(X\in\mathcal{B}\). Next, a submodular-constraint version of the optimality theorem for measurable circulations with cost is given in 6, using a separation argument and the potential representation theorem for measurable circulations. These two theorems extend Theorem 4.4 and Theorem 4.6 in [7].
Another topic of the paper is extreme feasible flows. For finite cases, the Birkhoff–von Neumann Theorem [8] describes a criterion for extreme points of the convex polytope formed by doubly stochastic matrices. A number of results follow in characterizing extreme measures with given marginals [9], [10], especially for the extreme coupling measures of Lebesgue measure on \([0,1]\); see, for example, [11], [12]. In [13]–[15], a necessary condition related to acyclicity for the support of extreme doubly stochastic measures is given. Motivated by the acyclicity criterion for residual graphs in the finite setting, we define the measurable residual graphs and give a characterization of extreme feasible submodular flows in 7 and also of reduced feasible submodular flows in 8.
As an application, we study transshipment problems on standard Borel spaces. We use 7 to characterize extreme feasible transshipments, and regarding the existence of feasible transshipments, a Hall-type criterion is given in 2, which can be viewed as a constrained version of [7]. As another application, 3 gives a fractional measurable analogue of Frank’s orientation theorem [16] for highly edge-connected graphs. However, obtaining a non-fractional measurable orientation is more delicate, and we pose it as an open problem.
To summarize, we establish a submodular flow theory in measurable spaces and extend the existence and optimality criteria of feasible flows in [7] to submodular flows. Further, we give characterizations of extreme submodular flows and extreme reduced flows.
The organization of the paper is as follows. In 2 we review the measure-theoretic flow framework of [7], recall the relevant facts on bounded continuous submodular set functions, and prove auxiliary results on basic minorizing charges. In 3 we establish the existence and optimality theorems for measurable submodular flows. In 4 we introduce measurable residual graphs and develop the extremality theory for submodular flows and reduced flows. Finally, 5 is devoted to applications in bipartite transshipment problems and measurable orientations.
Most definitions in this section are adapted from [7].
Definition 1 (Measure spaces). A standard Borel space is a measurable space isomorphic to the Borel \(\sigma\)-algebra of a Polish space. Throughout the paper we identify it with a Polish realization \((J,\mathcal{B})\). The diagonal \[\Delta_J:=\{(x,x)\in J\times J\;:\; x\in J\}\] belongs to \(\mathcal{B}^2\). We denote by \(\mathcal{M}(\mathcal{B})\) the set of all finite signed measures on \((J,\mathcal{B})\) and by \(\mathcal{M}_+(\mathcal{B})\) the set of all finite measures on \((J,\mathcal{B})\).
For any \(\alpha\in \mathcal{M}(\mathcal{B})\), the total variation norm of \(\alpha\) is \[\| \alpha \| :=\sup_{A \in \mathcal{B}} \alpha(A)-\inf_{B \in \mathcal{B}}\alpha(B).\] Then \(\|\cdot\|\) is a norm on \(\mathcal{M}(\mathcal{B})\) turning it into a Banach space, with \(\mathcal{M}_+(\mathcal{B})\) a closed cone of \(\mathcal{M}(\mathcal{B})\). This norm induces a metric on \(\mathcal{M}_+(\mathcal{B})\) called total variation distance, denoted by \(d_{\mathrm{tv}}(\alpha,\beta)=\| \alpha-\beta \|.\) Since \((J\times J,\mathcal{B}^2)\) is also a standard Borel space, we define \(\mathcal{M}(\mathcal{B}^2)\) and \(\mathcal{M}_+(\mathcal{B}^2)\) analogously.
For any \(A\in \mathcal{B}^2\) and any \(\mu\in \mathcal{M}(\mathcal{B}^2)\), we denote by \(\mu|_A\in \mathcal{M}(\mathcal{B}^2)\) the restriction measure such that \[\mu|_A(B)=\mu(A\cap B)\] for any \(B\in \mathcal{B}^2\). The transpose of \(E\in \mathcal{B}^2\) is the measurable subset \[E^*:=\{(x,y)\;:\; (y,x)\in E\}.\] The transpose of \(\mu\in \mathcal{M}(\mathcal{B}^2)\) is the unique signed measure \(\mu^*\) satisfying \(\mu^*(E)=\mu(E^*)\) for any \(E\in \mathcal{B}^2\). We write \(\mu^1,\mu^2\) for the marginals, i.e., the signed measures on \((J,\mathcal{B})\) such that for any \(X\in\mathcal{B}\), \[\mu^1(X)=\mu(X\times J), \qquad \mu^2(X)=\mu(J\times X).\]
The order on \(\mathcal{M}(\mathcal{B})\) is the usual measure order: \(\mu\le \nu\) means \(\nu-\mu\in \mathcal{M}_+(\mathcal{B})\).
By the Hahn decomposition given a standard Borel space \((J,\mathcal{B})\) and \(\mu\in\mathcal{M}(\mathcal{B})\), there exist disjoint sets \(P,N\in\mathcal{B}\), with \(P \cup N =J\) such that \(\mu|_P,-\mu|_N\in \mathcal{M}_+(\mathcal{B})\). We write \[\mu_+:=\mu|_P, \qquad \mu_-:=\mu|_N.\] Then \[\mu=\mu_+-\mu_-, \qquad |\mu|=\mu_++\mu_-.\] Here \(|\mu|\) is the total variation measure of \(\mu\).
For any two \(\mu,\nu\in\mathcal{M}(\mathcal{B})\), the join and meet are defined by \[\begin{align} \mu\vee\nu(X)&:=\sup\{ \mu(X_1)+\nu(X_2)\;:\; X=X_1\sqcup X_2, \;X_1,X_2\in\mathcal{B}\},\\ \mu\wedge\nu(X)&:=\inf\;\{ \mu(X_1)+\nu(X_2)\;:\; X=X_1\sqcup X_2, \;X_1,X_2\in\mathcal{B}\}. \end{align}\] It can be shown that \(\mu\wedge\nu,\mu\vee\nu\in\mathcal{M}(\mathcal{B})\) and if \(\mu,\nu\in\mathcal{M}_+(\mathcal{B})\), then \(\mu\wedge\nu,\mu\vee\nu\in\mathcal{M}_+(\mathcal{B})\).
For a signed measure \(\nu\), we call \(\nu\) absolutely continuous with respect to a positive measure \(\mu\), denoted by \(\nu\ll\mu\), if \(\mu(X)=0\) implies \(\nu(X)=0\) for any \(X\in\mathcal{B}\). A measure \(\alpha\) is supported on a measurable set \(S\in\mathcal{B}\) if \(\alpha(S^c)=0\).
Given two signed measures \(\lambda,\mu \in \mathcal{M}(\mathcal{B})\), we define the product measure, denoted by \(\lambda\otimes \mu\in\mathcal{M}(\mathcal{B}^2)\), to be \(\lambda\otimes \mu (X\times Y)=\lambda(X)\times \mu(Y)\) for any \(X,Y\in \mathcal{B}\).
For any \(\alpha\in \mathcal{M}(\mathcal{B})\) and any bounded measurable function \(v\) on \((J,\mathcal{B})\), the integral of \(v\) with respect to \(\alpha\) is denoted as \[\alpha(v):=\int_{J}v(x)\,\mathrm{d}\alpha(x).\]
The following is a compactness result about the space of measures.
Lemma 1 ([7]). Let \((J,\mathcal{B})\) be a standard Borel space and let \(\psi\in \mathcal{M}_+(\mathcal{B}^2)\). Then every sequence \((\mu_n)_{n\ge 1}\) in \[K_\psi:=\{\mu\in \mathcal{M}(\mathcal{B}^2): |\mu|\le \psi\}\] admits a subsequence \((\mu_{n_k})_{k\ge1}\) and a measure \(\mu\in K_\psi\) such that \[\mu_{n_k}(A)\to \mu(A)\qquad\text{for every }A\in\mathcal{B}^2.\]
Next we introduce the flow theory on measurable spaces.
Definition 2 (Measurable flows, circulations and potentials). Given a standard Borel space \((J,\mathcal{B})\), a flow on \(J\) is a finite signed measure \(\mu\in\mathcal{M}(\mathcal{B}^2)\). Given \(\sigma,\tau\in\mathcal{M}(\mathcal{B})\), a flow \(\mu\) is called a \(\sigma\)-\(\tau\) flow if \[\mu^1-\mu^2=\sigma-\tau.\] A circulation is a flow \(\alpha\in\mathcal{M}(\mathcal{B}^2)\) with \(\alpha^1=\alpha^2\). Note that a circulation is a \(0\)-\(0\) flow. A network system is a quadruple \((J,\mathcal{B},\alpha,\beta)\) with \(\alpha, \beta \in\mathcal{M}(\mathcal{B}^2)\). A flow \(\mu\) is feasible if \(\alpha\leq \mu\leq \beta\).
A measurable function \(F \colon J \times J \to \mathbb{R}\) is called a potential if there exists a bounded measurable function \(f \colon J \to \mathbb{R}\) such that for any \(x,y\in J\), we have \[F(x,y) = f(x) - f(y).\] Since adding a constant to \(f\) does not change the difference, one may assume that \(f\) is nonnegative. In particular, we can assume there exists \(D\in\mathbb{R}_+\) such that \(0\leq f<D\).
Remark 1. Every potential \(F(x,y)=f(x)-f(y)\) with \(0\leq f<D\) can be expressed as \[F(x,y) = \int_{0}^D \big( \mathbf{1}_{A_t}(x) - \mathbf{1}_{A_t}(y) \big) \mathrm{d} t,\] where \(A_t= \{ x \in J : f(x) \geq t \}\), \(0 \leq t \leq D\), is a measurable subset of \(J\) such that \[A_t \supseteq A_s,\;\forall\;t < s;\;\; A_D = \emptyset,\;\;A_0 = J.\]
The existence criterion of feasible flows is given as follows.
Theorem 1 ([7]). Given a standard Borel space \((J,\mathcal{B})\) and \(\alpha,\beta\in\mathcal{M}(\mathcal{B}^2)\), there exists a circulation \(\mu\) such that \(\alpha\leq \mu\leq \beta\) if and only if \(\alpha\leq \beta\) and \[\alpha(X\times X^c)\leq \beta(X^c\times X) \quad \text{ for all X\in\mathcal{B}}.\]
Corollary 1. Given a standard Borel space \((J,\mathcal{B})\), two signed measures \(\sigma,\tau\in\mathcal{M}(\mathcal{B})\) with \(\sigma(J)=\tau(J)\) and two signed measures \(\alpha,\beta\in\mathcal{M}(\mathcal{B}^2)\) with \(\alpha \le \beta\), there exists a \(\sigma\)-\(\tau\) flow \(\mu\) such that \(\alpha\leq \mu\leq \beta\) if and only if \[\alpha(X\times X^c)-\beta(X^c\times X)\leq \sigma(X)-\tau(X) \quad \text{for all X\in\mathcal{B}}.\]
Proof. Define \(J':=J\cup \{s,t\}\) and let \(\mathcal{B}'\) be the \(\sigma\)-algebra generated by \(\mathcal{B}\cup \{\{s\},\{t\}\}\). Let \[\begin{align} \alpha'(E)\; (\text{w.r.t. }\beta'(E)):=\left\{ \begin{aligned} &\alpha(E)&& (\text{w.r.t. }\beta(E)),\;& &E\subseteq J\times J;\\ &\sigma(X)&& (\text{w.r.t. }\sigma(X)),\; & &E=\{s\}\times X\subseteq\{s\}\times J;\\ &\tau(X)&& (\text{w.r.t. }\tau(X)),\;& &E=X\times \{t\}\subseteq J\times \{t\};\\ &0&& (\text{w.r.t. }0),\; && E\subseteq (J\times \{s\})\cup (\{t\}\times J)\cup( \{s\}\times\{t\});\\ &\sigma(J)=\tau(J)&& (\text{w.r.t. }\sigma(J)=\tau(J)),\;&& E=\{t\}\times \{s\}, \end{aligned} \right. \end{align}\] and extend them to \({\mathcal{B}'}^2\). Since \(\alpha \le \beta\), we have \(\alpha'\le \beta'\). Apply 1 with \(J'\), \(\mathcal{B}'\), \(\alpha'\) and \(\beta'\) in place of \(J\), \(\mathcal{B}\), \(\alpha\) and \(\beta\), such flow exists if and only if for any \(X\in \mathcal{B}'\), we have \(\alpha'(X\times X^c)\leq \beta'(X^c\times X)\). Since \(\sigma(J)=\tau(J)\), it is easy to check that this is equivalent to saying for any \(X\subseteq J\), we have \[\phantom{ssssssssssssssssssssssssss}\alpha(X\times X^c)-\beta(X^c\times X)\leq \sigma(X)-\tau(X).\phantom{ssssssssssssssssssssssssss}\qedhere\] ◻
Two extra lemmas are needed.
Lemma 2 ([7]). Let \(K_{1},\dots,K_{n}\) be open convex sets in a Banach space \((X, \| \cdot \|)\). Then \(K_{1}\cap \cdots \cap K_{n}=\emptyset\) if and only if there are bounded linear functionals \(\mathcal{L}_{1},\dots,\mathcal{L}_{n}\) on \(X\) and real numbers \(a_{1},\dots,a_{n}\) such that \(\mathcal{L}_{1}+\cdots +\mathcal{L}_{n}=0\), \(a_{1}+\cdots+a_{n}=0\), and for each \(i\), either \(\mathcal{L}_{i}=0\) and \(a_{i}=0\), or \(\mathcal{L}_{i}(x)>a_{i}\) for \(x \in K_{i}\), and for at least one \(i\) the second possibility holds.
Lemma 3 ([7]). Given a standard Borel space \((J,\mathcal{B})\) and a flow \(\alpha\in \mathcal{M}(\mathcal{B}^2)\), then \(\alpha\) is a circulation if and only if \(\alpha(F)=0\) for any potential \(F\) on \(J\times J\). Further, given a measure \(\psi\in\mathcal{M}_+(\mathcal{B}^2)\) and a bounded linear functional \(\mathcal{L}\) on the linear subspace \(\{\mu\in\mathcal{M}(\mathcal{B}^2)\;:\: \mu\ll \psi \}\) with \(\mathcal{L}(c)=0\) for all circulations \(c\ll \psi\), there exists a potential \(F\) such that \(\mathcal{L}(\mu)=\mu(F)\) for all \(\mu\ll\psi\).
Definition 3. A lattice is a pair \((J,\mathcal{B})\) such that \(J\) is a set and \(\mathcal{B}\) is a family of subsets of \(J\) closed under finite union and intersection. A set algebra is a lattice containing \(J\) and closed under taking complement. A submodular set function is a function \(f\colon \mathcal{B}\to\mathbb{R}\) such that for all \(A,B\in \mathcal{B}\), \[f(A)+f(B)\geq f(A\cap B)+f(A\cup B).\] It is supermodular if the inequality is reversed, and modular if the equality holds. A charge is a finitely additive set function. Note that a modular set function \(\mu\) is a charge if and only if \(\mu(\emptyset)=0\). A set function \(\varphi\) is called continuous if for any \(A\in \mathcal{B}\) and any sequence \(\{A_n\}_{n=1}^\infty\subseteq \mathcal{B}\) such that \(\lim_{n\to\infty}\mathbf{1}_{A_n}(x)=\mathbf{1}_A(x)\) for any \(x\in J\), we have \(\lim_{n\to\infty}\varphi(A_n)=\varphi(A)\).
In this paper, we focus on bounded continuous submodular set functions \(\varphi\) on a standard Borel space \((J,\mathcal{B})\) with \(\varphi(\emptyset)=0\); in most applications we also assume \(\varphi(J)=0\).
Definition 4. Let \(\varphi\) be a submodular function on a standard Borel space \((J,\mathcal{B})\) with \(\varphi(\emptyset)=0\). The set of basic minorizing charges, denoted by \(\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\), is defined by \[\mathop{\mathrm{\mathsf{bmm}}}(\varphi):=\{\beta\;:\;\text{\beta is a charge, } \beta\leq \varphi, \beta(J)=\varphi(J)\},\] and \(\mathop{\mathrm{\mathsf{bmm}}}_+(\varphi)\) is defined by \[\mathop{\mathrm{\mathsf{bmm}}}_+(\varphi):=\{\beta\;:\;\text{\beta is a charge, }0\leq \beta\leq \varphi, \beta(J)=\varphi(J)\}.\]
The following 4 is folklore and similar statements can be found in [17]. For the sake of completeness we give a proof. We first introduce two properties. For a subset \(K\subseteq \mathcal{M}(\mathcal{B}^2)\), \(K\) is called uniformly countably additive if for any decreasing sequence \(\{E_i\}_{i=1}^\infty \subset \mathcal{B}\) with \(\bigcap_{i=1}^\infty E_i=\emptyset\) and any \(\epsilon>0\), there exists \(N_\epsilon\) such that for any \(n\geq N_\epsilon\) and \(\mu\in K\), we have \(|\mu(E_n)|<\epsilon\); \(K\) is called uniformly absolutely continuous with respect to some \(\lambda\in \mathcal{M}_+(\mathcal{B}^2)\) if for any \(\epsilon>0\) there exists \(\delta>0\) such that for any \(E\in \mathcal{B}\) with \(\lambda(E)<\delta\) we have \(\sup_{\mu\in K}|\mu(E)|<\epsilon\). These two properties are equivalent as stated below.
Theorem 2 ([18]). Given a standard Borel space \((J,\mathcal{B})\), let \(K\) be a bounded subset of \(\mathcal{M}(\mathcal{B}^2)\) in the total variation norm. Then \(K\) is uniformly countably additive if and only if there exists \(\lambda\in\mathcal{M}_+(\mathcal{B}^2)\) such that \(K\) is uniformly absolutely continuous with respect to \(\lambda\).
Now we can state and prove the following lemma.
Lemma 4. Let \((J,\mathcal{B})\) be a standard Borel space and let \(\varphi\) be a bounded continuous submodular set function on \(\mathcal{B}\) with \(\varphi(\emptyset)=0\). Then any charge \(\alpha\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) is countably additive, and hence \(\alpha\in\mathcal{M}(\mathcal{B})\). Moreover, there exists some \(\lambda_\varphi\in \mathcal{M}_+(\mathcal{B})\) such that \(\alpha\ll\lambda_\varphi\) for any \(\alpha\in \mathop{\mathrm{\mathsf{bmm}}}(\varphi)\).
Proof. Let \(X\in\mathcal{B}\) and \(\{X_n\}_{n=1}^\infty\subseteq \mathcal{B}\) be pairwise disjoint with \(X=\bigsqcup_{n=1}^\infty X_n\). Let \[Y_k:=\bigsqcup_{n=1}^k X_n,\qquad Z_k:=\bigsqcup_{n=k+1}^\infty X_n.\] Since \(\mathcal{B}\) is a \(\sigma\)-algebra, \(Y_k,Z_k\in\mathcal{B}\). Since \(\varphi\) is continuous, we have \(\lim_{k\to\infty}\varphi(Z_k)=\varphi(\emptyset)=0\) and \(\lim_{k\to\infty}\varphi(Z_k^c)=\varphi(J)\).
For every \(k\), finite additivity gives \(\alpha(X)=\alpha(Y_k)+\alpha(Z_k)\). Moreover, \[\varphi(J)-\varphi(Z_k^c)\le \varphi(J)-\alpha(Z_k^c)=\alpha(Z_k)\le\varphi(Z_k),\] so \(\lim_{k\to\infty}\alpha(Z_k)=0\). Hence if \(\lim_{k\to\infty}\alpha(Y_k)\) exists, then \[\alpha(X)=\lim_{k\to\infty}\alpha(Y_k).\]
It remains to show that this limit always exists. Suppose not. There exists \(\epsilon>0\) and a subsequence \(\{Y_{n_k}\}\) such that \[|\alpha(Y_{n_{2k+1}})-\alpha(Y_{n_{2k+2}})|>\epsilon, \quad k\geq 1.\] Let \(W_k:=Y_{n_{2k+2}}\setminus Y_{n_{2k+1}}\). Then \(\liminf_{k\to\infty} |\alpha(W_k)|>\epsilon\). On the other hand, \[\varphi(J)-\varphi(W_k^c)\leq \varphi(J)-\alpha(W_k^c) = \alpha(W_k)\leq \varphi(W_k).\] By continuity of \(\varphi\), both the left and right bounds tend to \(0\), so \(\lim_{k\to\infty}\alpha(Z_k)=0\), a contradiction. Thus \(\alpha\) is countably additive.
Let \(M:=\sup_{X\in\mathcal{B}}|\varphi(X)|<\infty\). For every \(X\in\mathcal{B}\), \(\varphi(J)-\varphi(X^c)\leq \alpha(X)\leq \varphi(X)\), and hence \(-2M\le\alpha(X)\le M\). Therefore \(\|\alpha\|=\sup_X\alpha(X)-\inf_X\alpha(X)\le3M\), so \(\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) is bounded in the total variation norm.
Finally, let \(\{E_i\}_{i=1}^\infty \subset \mathcal{B}\) be decreasing such that \(\bigcap_{i=1}^\infty E_i=\emptyset\) and \(\epsilon>0\). Since \(E_n^c\uparrow J\) pointwise, continuity of \(\varphi\) gives \(\varphi(E_n)\to0\) and \(\varphi(E_n^c)\to\varphi(J)\). The same two-sided estimate gives \[\sup_{\alpha\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)}|\alpha(E_n)|\to0.\]
By 2, there exists \(\lambda_\varphi\in\mathcal{M}_+(\mathcal{B})\) such that \(\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) is uniformly absolutely continuous with respect to \(\lambda_\varphi\). In particular, every \(\alpha\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) satisfies \(\alpha\ll\lambda_\varphi\). ◻
By 4, if \(\varphi\) is bounded and continuous, then \(\mathop{\mathrm{\mathsf{bmm}}}(\varphi), \mathop{\mathrm{\mathsf{bmm}}}_+(\varphi) \subseteq \mathcal{M}(\mathcal{B})\).
We also need the following two basic properties about submodular set functions.
Theorem 3 ([1]). Let \((J,\mathcal{B})\) be a set algebra and \(\alpha,\beta\) be bounded set functions on \((J,\mathcal{B})\), where \(\alpha\) is supermodular and \(\beta\) is submodular. If \(\alpha\leq \beta\), then there exists a modular set function \(\gamma\) on \((J,\mathcal{B})\) such that \(\alpha\leq \gamma\leq \beta\) and \(\gamma(J)=\beta(J)\).
Theorem 4 ([1]). Let \(\varphi\) be a bounded submodular set function on a set algebra \((J,\mathcal{B})\) such that \(\varphi(\emptyset)=0\), and let \(\mathcal{L}\subseteq \mathcal{B}\) be a lattice containing \(\emptyset\) and \(J\). Assume that \(\varphi\) is modular on \(\mathcal{L}\). Then there exists \(\alpha \in \mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) such that \(\alpha(S)=\varphi(S)\) for every \(S\in \mathcal{L}\). If \(\varphi\) is increasing, then \(\alpha\geq 0\).
In the end, we introduce the Choquet integral of submodular set functions, transforming set functions to operators on bounded measurable functions.
Definition 5. Given a set algebra \((J,\mathcal{B})\) and a bounded submodular set function \(\varphi\) on \((J,\mathcal{B})\), for any function \(f \in \mathop{\mathrm{\mathsf{Bd}}}(\mathcal{B})\), where \(\mathop{\mathrm{\mathsf{Bd}}}(\mathcal{B})\) denotes the set of all bounded \(\mathcal{B}\)-measurable functions on \(J\), choose \(C\in\mathbb{R}\) with \(f+C\geq0\) and define the Choquet integral as \[\hat{\varphi}(f):= \int f \, \mathrm{d}\varphi := \int_0^\infty \varphi(\{f+C\geq t\}) \, \mathrm{d} t-C \varphi(J).\] This definition is independent of \(C\) since \[\begin{align} \int_0^\infty \varphi(\{f+C_1+C_2\geq t\}) \, \mathrm{d} t&=\int_0^{C_2} \varphi(\{f+C_1+C_2\geq t\}) \, \mathrm{d} t+ \int_{C_2}^\infty \varphi(\{f+C_1+C_2\geq t\}) \, \mathrm{d} t\\ &= \int_0^\infty \varphi(\{f+C_1\geq t\}) \, \mathrm{d} t+C_2\varphi(J). \end{align}\]
In the spirit of classical submodular flows, we give the definition of submodular flows on a standard Borel space as follows.
Definition 6 (Boundary operator and cut function). Given a standard Borel space \((J,\mathcal{B})\) and \(\mu\in \mathcal{M}(\mathcal{B}^2)\), define the boundary of \(\mu\) by \[\partial\mu(X):=\mu(X\times X^c)-\mu(X^c\times X), \quad X\in\mathcal{B}.\] Then \(\partial\mu=\mu^1-\mu^2\), so \(\partial:\mathcal{M}(\mathcal{B}^2)\to \mathcal{M}(\mathcal{B})\) is a linear operator. For \(\alpha\), \(\beta\in \mathcal{M}(\mathcal{B}^2)\) with \(\alpha\leq \beta\), the cut function \(\kappa_{\alpha,\beta}\) is defined by \[\kappa_{\alpha,\beta}(X):=\beta(X\times X^c)-\alpha(X^c\times X), \quad X\in\mathcal{B}.\]
Definition 7 (Feasible submodular flows). Let \((J,\mathcal{B})\) be a standard Borel space and let \(\varphi : \mathcal{B}\to \mathbb{R}\) be a bounded continuous submodular function with \(\varphi(\emptyset)=\varphi(J)=0\), a submodular flow with respect to \(\varphi\) is a signed measure \(\mu \in \mathcal{M}(\mathcal{B}^2)\) such that \[\partial \mu(X) \leq \varphi(X) \qquad \textrm{ for all } X\in \mathcal{B}.\] Given \(\alpha,\beta\in\mathcal{M}(\mathcal{B}^2)\) with \(\alpha\leq \beta\), a flow \(\mu\) is feasible with respect to \((\alpha,\beta)\) if \(\alpha\leq \mu\leq \beta\). The tuple \((J,\mathcal{B},\alpha,\beta,\varphi)\) is called a submodular network system. If \(v\colon J\times J\to\mathbb{R}_{\geq 0}\) is bounded and measurable, the cost with respect to \(v\) of a flow \(\mu\) is defined as \[\mu(v)=\int_{J \times J}\,v(x)\,\mathrm{d}\mu(x).\] For simplicity, we just say \(\mu\) is a feasible submodular flow if the system is clear.
In this subsection, given a submodular network system, we characterize the condition for the existence of a feasible submodular flow. We first give several lemmas about the cut function and base polytope intersection.
Lemma 5. Given a network system \((J,\mathcal{B},\alpha,\beta)\) with \(\alpha \le \beta\), the cut function \(\kappa_{\alpha,\beta}\) is bounded, continuous, and submodular. Moreover, \[\kappa_{\alpha,\beta}(\emptyset)=\kappa_{\alpha,\beta}(J)=0.\]
Proof. Boundedness is immediate from the finiteness of \(\alpha\) and \(\beta\). If \(\mathbf{1}_{X_n}\to\mathbf{1}_X\) pointwise, then \(\mathbf{1}_{X_n\times X_n^c}\to\mathbf{1}_{X\times X^c}\) and \(\mathbf{1}_{X_n^c\times X_n}\to\mathbf{1}_{X^c\times X}\) pointwise on \(J\times J\). Dominated convergence with respect to \(|\alpha|+|\beta|\) gives \(\kappa_{\alpha,\beta}(X_n)\to\kappa_{\alpha,\beta}(X)\), so \(\kappa_{\alpha,\beta}\) is continuous.
For submodularity, decompose \(J\) according to the four regions \(X\cap Y\), \(X\setminus Y\), \(Y\setminus X\), and \((X\cup Y)^c\). For every finite signed measure \(m\) on \(J\times J\), one has \[\begin{align} &m(X\times X^c)+m(Y\times Y^c)-m((X\cup Y)\times (X\cup Y)^c)-m((X\cap Y)\times (X\cap Y)^c)\\ =\;& m\big( (X\setminus Y)\times (Y\setminus X)\big)+m\big((Y\setminus X)\times (X\setminus Y)\big)\ge 0. \end{align}\] Applying this to \(m=\beta\) and, with \(X,Y\) replaced by \(X^c,Y^c\), to \(m=\alpha\), we get \[\begin{align} &\kappa_{\alpha,\beta}(X)+\kappa_{\alpha,\beta}(Y)-\kappa_{\alpha,\beta}(X\cup Y)-\kappa_{\alpha,\beta}(X\cap Y)\\ =\;&(\beta-\alpha)\big((X\setminus Y)\times (Y\setminus X)\big)+(\beta-\alpha)\big((Y\setminus X)\times (X\setminus Y)\big)\ge 0, \end{align}\] since \(\beta\ge \alpha\). Hence \(\kappa_{\alpha,\beta}\) is submodular. ◻
Proof. For any \(X,Y \in \mathcal{B}\), we have \[\begin{align} &\kappa_{\alpha,\beta}(X)+\kappa_{\alpha,\beta}(Y)-\kappa_{\alpha,\beta}(X\cup Y)-\kappa_{\alpha,\beta}(X\cap Y)\\ =&\beta(X\times X^c)-\alpha(X^c\times X)+\beta(Y\times Y^c)-\alpha(Y^c\times Y)\\ -&(\beta(X\cup Y\times (X\cup Y)^c)-\alpha(X\cup Y\times (X\cup Y)^c)-(\beta(X\cap Y\times (X\cap Y)^c)-\alpha(X\cap Y\times (X\cap Y)^c)\\ =&\beta((X\setminus Y)\times (X\setminus Y)^c)-\alpha((X\setminus Y)^c\times(X\setminus Y))+\beta((Y\setminus X)\times (Y\setminus X)^c)-\alpha((Y\setminus X)^c\times(Y\setminus X))\\ \ge& 0. \end{align}\] And we complete the proof. ◻
Lemma 6. Let \((J,\mathcal{B},\alpha,\beta)\) be a network system with \(\alpha \le \beta\). Then \[\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{\alpha,\beta}) =\{\partial\mu\;:\; \mu\in\mathcal{M}(\mathcal{B}^2),\; \alpha\leq \mu\leq \beta \}.\]
Proof. Let \(\mu\in\mathcal{M}(\mathcal{B}^2)\) satisfy \(\alpha\leq \mu\leq \beta\). Then for every \(X \in \mathcal{B}\), we have \[\partial\mu(X)=\mu(X\times X^c)-\mu(X^c\times X)\leq \beta(X\times X^c)-\alpha(X^c\times X)=\kappa_{\alpha,\beta}(X).\] Also, \(\partial\mu(J) = 0 =\kappa_{\alpha,\beta}(J)\). Thus \(\partial \mu\in \mathop{\mathrm{\mathsf{bmm}}}(\kappa_{\alpha,\beta})\).
Conversely, let \(\gamma\in \mathop{\mathrm{\mathsf{bmm}}}(\kappa_{\alpha,\beta})\). By 5 and 4, \(\gamma\) is a finite signed measure. Since \(\gamma(J)=\kappa_{\alpha,\beta}(J)=0\), we have \(\gamma(X)=-\gamma(X^c)\) for all \(X \in \mathcal{B}\). Since \(\gamma \le \kappa_{\alpha,\beta}\), applying this inequality to \(X^c\) gives \[\gamma(X^c)\le\kappa_{\alpha,\beta}(X^c)=\beta(X^c\times X)-\alpha(X\times X^c).\] Therefore \[\alpha(X\times X^c)-\beta(X^c\times X)\le -\gamma(X^c)=\gamma(X).\] By 1 with \(\sigma=\gamma\) and \(\tau = 0\), there exists a \(\gamma\)-0 flow \(\mu \in \mathcal{M}(\mathcal{B}^2)\) such that \(\alpha\leq \mu\leq \beta\). Hence \(\partial \mu = \gamma\). ◻
Lemma 7. Given a standard Borel space \((J,\mathcal{B})\) and two bounded submodular set functions \(\varphi,\psi\) such that \(\varphi(J)=\psi(J)\) and \(\varphi(\emptyset)=\psi(\emptyset)=0\), we have \[\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi) \neq \emptyset\] if and only if \[\psi(J)-\psi(X^c)\leq \varphi(X) \quad\text{for any X \in \mathcal{B}.}\]
Proof. If \(\mu\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi)\), then for any \(X \in \mathcal{B}\), \[\varphi(X)+\psi(X^c)\geq \mu(X)+\mu(X^c)=\mu(J)=\psi(J),\] which gives the disired inequality.
Conversely, assume \(\psi(J)-\psi(X^c)\leq \varphi(X)\) for all \(X \in \mathcal{B}\) and define the supermodular set function \[\phi\colon \mathcal{B}\to \mathbb{R}, \quad\phi(X):=\psi(J)-\psi(X^c).\] Then \(\phi\leq \varphi\), \(\phi(\emptyset)=\varphi(\emptyset)=0\), and \(\phi(J)=\varphi(J)=\psi(J)\). By 3, there exists a modular set function \(\mu\) such that \(\phi\leq \mu\leq \varphi\), \(\mu(\emptyset)=0\) and \(\mu(J)=\psi(J)\). For any \(X\in\mathcal{B}\), we have \[\mu(X)=\mu(J)-\mu(X^c)\leq \psi(J)-\phi(X^c)=\psi(X).\] Thus \(\mu\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi)\). ◻
Theorem 5 (Existence Theorem). Given a submodular network system \((J,\mathcal{B},\alpha,\beta,\varphi)\), there exists a feasible submodular flow if and only if for any \(X\in\mathcal{B}\), we have \[\alpha(X\times X^c)-\beta(X^c\times X)\leq \varphi(X).\]
Proof. By 6, a feasible submodular flow exists if and only if \(\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\kappa_{\alpha,\beta}) \neq \emptyset\). By 5 and 7, this is equivalent to \[\kappa_{\alpha,\beta}(J)-\kappa_{\alpha,\beta}(X^c)\leq \varphi(X) \quad \text{for any X\in\mathcal{B}}.\] Since \(\kappa_{\alpha,\beta}(J)=0\), this is precisely \[\phantom{ssssssssssssssssssssssss}\alpha(X\times X^c)-\beta(X^c\times X)\leq \varphi(X)\quad \text{for any X\in\mathcal{B}}.\phantom{ssssssssssssssssssss}\qedhere\] ◻
If \(J\) is finite, 5 reduces to the classical feasibility theorem for discrete submodular flows:
Corollary 2 (Edmonds–Giles Feasibility Theorem [4]). Let \(G=(V, E)\) be a finite directed graph with edge set \(E \subseteq V \times V\). Let \(l, u \colon E \to \mathbb{R}\) be edge capacity functions satisfying \(l \le u\), and let \(b \colon 2^V \to \mathbb{R}\) be a submodular set function with \(b(\emptyset) = b(V) = 0\). We use \(\delta^+(X)\) and \(\delta^-(X)\) denote the set of edges leaving and entering \(X\), respectively. Then the following two statements are equivalent.
There exists a discrete flow \(x \colon E \to \mathbb{R}\) satisfying \[l(e) \le x(e) \le u(e), \;\forall \,e \in E;\quad \partial x(X) \le b(X) , \;\forall \, X \subseteq V,\] where \[\partial x(X)=\sum_{e\in \delta^+(X)}x(e)- \sum_{e\in \delta^-(X)}x(e).\]
For any \(X \subseteq V\), \[\sum_{e\in \delta^+(X)}l(e) - \sum_{e\in \delta^-(X)}u(e) \le b(X).\]
Proof. We can naturally embed this discrete problem into our measurable framework. Let \(J = V\) and \(\mathcal{B}=2^V\). Define capacity measures \(\alpha, \beta \in \mathcal{M}(\mathcal{B}^2)\) as follows: \[\alpha(S) := \sum_{e \in S \cap E} l(e), \qquad \beta(S) := \sum_{e \in S \cap E} u(e) ,\; S \subseteq V \times V.\] Then \((J,\mathcal{B},\alpha,\beta,b)\) is a submodular network system. Any feasible measure \(\mu\) corresponds bijectively to a discrete flow \(x:E\to\mathbb{R}\) by setting \(x(e)=\mu(\{e\})\). Conversely, every such discrete flow defines a measure supported on \(E\). Then the corollary follows by 5. ◻
Example 1. We give a simple example showing that 5 is not merely a reformulation of 2. Let \(J=[0,1]\), \(\mathcal{B}\) be the Borel \(\sigma\)-algebra generated by open intervals and \(\lambda\) be the Lebesgue measure on \(J\). Put \[\Omega:=\{(x,y)\in[0,1]^2:x<y\}, \qquad \psi:=(\lambda\otimes\lambda)|_\Omega.\] Thus \(\psi\) may be viewed as a continuum of directed arcs from smaller points to larger points. Fix \(0<r\le1\), and define lower and upper capacity measures by \[\alpha:=r \psi, \qquad \beta:=\psi.\] Then \(\alpha\le\beta\). For a parameter \(q\ge0\), define \[\varphi_q(X):=q\lambda(X)\lambda(X^c),\qquad X\in\mathcal{B}.\] The function \(\varphi_q\) is bounded and continuous. Moreover, it is submodular, since for any \(A,B\in\mathcal{B}\), \[\varphi_q(A)+\varphi_q(B)-\varphi_q(A\cup B)-\varphi_q(A\cap B) =2q\lambda(A\setminus B)\lambda(B\setminus A)\ge0.\] Also \(\varphi_q(\emptyset)=\varphi_q(J)=0\).
For every \(X\in\mathcal{B}\), we have \[\alpha(X\times X^c)-\beta(X^c\times X) \le \alpha(X\times X^c) =r m(X\times X^c) \le r(\lambda\otimes\lambda)(X\times X^c) =r\lambda(X)\lambda(X^c).\] Hence, if \(q\ge r\), then \[\alpha(X\times X^c)-\beta(X^c\times X)\le\varphi_q(X)\] for all \(X\in\mathcal{B}\). By 5, there exists a feasible submodular flow \(\mu\in\mathcal{M}(\mathcal{B}^2)\) satisfying \(\alpha\le\mu\le\beta\) and \(\partial\mu\le\varphi_q\).
The threshold \(q\ge r\) is sharp for this family. Indeed, if \(q<r\) and \(X=[0,t]\) with \(0<t<1\), then \[\alpha(X\times X^c)=rt(1-t), \qquad \beta(X^c\times X)=0,\] while \(\varphi_q(X)=qt(1-t)\). Thus the cut condition in 5 fails, and no feasible submodular flow exists when \(q<r\).
In this subsection, we fix \(\nu\in\mathcal{M}_+(\mathcal{B}^2)\) and restrict \(\mathcal{M}(\mathcal{B}^2)\) to those measures absolutely continuous with respect to \(\nu\), so that we can apply 3. We first give the following lemma about optimizing values of the integral of a potential on measures in the base polytope of a submodular set function.
Lemma 8. Given \((J,\mathcal{B})\) and a bounded continuous submodular set function \(\varphi\) on \(\mathcal{B}\) with \(\varphi(\emptyset)=\varphi(J)=0\), let \(\lambda_\varphi\in \mathcal{M}_+(\mathcal{B})\) be the measure given by 4 such that every \(\mu\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) satisfies \(\mu\ll\lambda_\varphi\). Then for any potential \(F\colon J\times J\to\mathbb{R}\) with \(F(x,y)=f(x)-f(y)\) with \(f \ge 0\) on \(J\), we have \[\begin{align} \max&\{\mu(F)\;:\; \mu\in\mathcal{M}(\mathcal{B}^2),\; \partial\mu \leq \varphi\}=\hat{\varphi}(f)\\ \min&\{\mu(F)\;:\; \mu\in\mathcal{M}(\mathcal{B}^2),\; \partial\mu \leq \varphi\}=-\hat{\varphi}(-f). \end{align}\] Moreover, the maximum and minimum can be attained by signed measures absolutely continuous with respect to \(\lambda_\varphi\otimes \lambda_\varphi\).
Proof. Assume \(0\leq f< C\) and let \(A_t=\{x\in J\;:\;f(x)\geq t\}\). By 1, \[F(x,y)=\int_0^C\big(\mathbf{1}_{A_t}(x)-\mathbf{1}_{A_t}(y)\big)\,\mathrm{d} t.\] For any \(\mu\in \mathcal{M}(\mathcal{B}^2)\), Fubini’s Theorem gives \[\begin{align} \mu(F)&=\int_{J\times J}\int_0^C\big(\mathbf{1}_{A_t}(x)-\mathbf{1}_{A_t}(y)\big)\,\mathrm{d} t\,\mathrm{d}\mu(x,y)=\int_0^C\big(\mu(A_t\times J)-\mu(J\times A_t)\big)\,\mathrm{d} t\\ &=\int_0^C\partial \mu (A_t)\,\mathrm{d} t\;\leq \;\int_0^C\varphi(A_t)\,\mathrm{d} t\;=\;\hat{\varphi}(f). \end{align}\] Similarly, with \(B_t=\{x\in J\,:\,f(x)\leq t\}\) we have \[F(x,y)=-\int_{0}^C\big(\mathbf{1}_{B_t}(x)-\mathbf{1}_{B_t}(y)\big)\, \mathrm{d} t,\] and using \(\varphi(J)=0\), \[\begin{align} \mu(F)&=-\int_0^C\big(\mu(B_t\times J)-\mu(J\times B_t)\big)\,\mathrm{d} t=-\int_0^C\partial \mu (B_t)\,\mathrm{d} t\geq -\int_0^C\varphi(B_t)\,\mathrm{d} t\\ &=-\int_0^C\varphi(B_{C-t})\,\mathrm{d} t=-\int_0^C\varphi(\{C-f\geq t\})\,\mathrm{d} t=-\hat{\varphi}(C-f)=-\hat{\varphi}(-f). \end{align}\]
We next prove that the maximum and minimum can be attained. Let \[\mathcal{C} := \{A_t : 0\le t\le C\}.\] Then \(\mathcal{C}\) is a lattice containing \(\emptyset\) and \(J\). Moreover, since \(\mathcal{C}\) is a chain, the restriction \(\varphi|_{\mathcal{C}}\) is modular. Therefore, by 4, there exists \(\alpha\in\mathop{\mathrm{\mathsf{bmm}}}(\varphi)\) such that \[\alpha(S)=\varphi(S)\qquad \text{for all }S\in\mathcal{C}.\] It is therefore enough to construct a flow \(\mu\in \mathcal{M}(\mathcal{B}^2)\) such that \(\partial\mu=\alpha\). Indeed, for such a \(\mu\), \[\mu(F) = \int_0^C \partial\mu(A_t)\,\mathrm{d} t = \int_0^C \alpha(A_t)\,\mathrm{d} t = \int_0^C \phi(A_t)\,\mathrm{d} t = \widehat\phi(f).\] Let \(\alpha=\alpha_1-\alpha_2\) be the Hahn decomposition of \(\alpha\) and \(\alpha_i\) is supported on \(X_i\), \(i=1,2\), such that \(J=X_1\sqcup X_2\). Since \(\alpha(J)=0\), we define \(a=\alpha_1(X_1)=\alpha_2(X_2)\). If \(a=0\), then \(\alpha=0=\partial 0\) and \(\mu=0\) attains maximum. Now we assume \(a>0\). Let \[\nu_\alpha=\dfrac{2}{a}(\alpha_1+\alpha_2)\otimes (\alpha_1+\alpha_2)\in \mathcal{M}_+(\mathcal{B}^2).\]
We claim that for any \(S\in \mathcal{B}\) we have \[\nu_\alpha(S\times S^c)\geq \alpha(S).\] Let \(S=S_1\sqcup S_2\) such that \(S_1\subseteq X_1\) and \(S_2\subseteq X_2\). Then \(\alpha(S)=\alpha_1(S_1)-\alpha_2(S_2)\). Let \(T_1=X_1\setminus S_1\) and \(T_2=X_2\setminus S_2\). If \(\alpha_1(S_1)\leq \alpha_1(T_1)\). Then \[\nu_\alpha(S\times S^c)\geq\dfrac{2}{a}\cdot\alpha_1(S_1)\cdot \alpha_1(T_1)\geq \dfrac{2}{a}\cdot\alpha_1(S_1)\cdot\dfrac{a}{2}\geq\alpha_1(S_1)\geq \alpha(S).\] If \(\alpha_1(S_1)> \alpha_1(T_1)\). Since \(\alpha_1(S_1)-\alpha_2(S_2)=\alpha_2(T_2)-\alpha_1(T_1)\leq \alpha_2(T_2)\), we have \[\nu_\alpha(S\times S^c)\geq\dfrac{2}{a}\cdot\alpha_1(S_1)\cdot \alpha_2(T_2)\geq \dfrac{2}{a}\cdot\dfrac{a}{2}\cdot\alpha_2(T_2)\geq\alpha(S).\] By 1, there exists \(\mu\in \mathcal{M}(\mathcal{B}^2)\) such that \(0\leq \mu\leq \nu_\alpha\) and \(\partial \mu=\alpha\). Then \(\mu(F)=\hat{\varphi}(f)\). Note that \(\alpha_1,\alpha_2\ll \lambda_\varphi\) and thus \(\nu_\alpha\ll\lambda_\varphi\otimes \lambda_\varphi\). As a result, \(\mu\ll\lambda_\varphi\otimes \lambda_\varphi\).
For the minimum, applying the same argument to the chain \(\mathcal{C}':=\{B_t\}_{0\leq t\leq C}\) gives a signed measure \(\beta\leq \varphi\) with \(\beta|_{\mathcal{C}'}=\varphi|_{\mathcal{C}'}\) and a flow \(\mu'\in\mathcal{M}(\mathcal{B}^2)\) with \(\partial \mu'=\beta\) and \(\mu'(F)=-\hat{\varphi}(-f)\). Still we have \(\mu'\ll\lambda_\varphi\otimes \lambda_\varphi\). ◻
The following theorem is a submodular flow version of [7], with 8 providing the potential-optimization step. For functions on \(J\), we denote by \(g^+\) and \(g^-\) the two functions \(g\vee 0\) and \((-g)\vee 0\) and it is easy to see that \(g=g^+-g^-\).
Theorem 6 (Optimality Theorem). Given a submodular network system with cost \((J,\mathcal{B},\alpha,\beta,\varphi,v)\), there exists a feasible submodular flow \(\mu\) such that \(\mu(v)=c\) if and only if there exists a feasible submodular flow and for any potential \(F(x,y)=f(x)-f(y)\) and \(f\geq 0\), we have \[\begin{align} \label{eq:dualineqonpotentialF} \alpha((F+v)^+)-\beta((F+v)^-)-\hat{\varphi}(f)\;\leq \;c \;\leq \;\beta((F+v)^+)-\alpha((F+v)^-)+\hat{\varphi}(-f). \end{align}\qquad{(1)}\] Consequently, \[\inf_{\mu \in \mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)}\mu(v)= \sup_{F=f(x)-f(y),\;f\ge0} \left[ \alpha((F+v)^+)-\beta((F+v)^-)-\hat{\varphi}(f)\right],\] and \[\sup_{\mu \in \mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)}\mu(v)= \inf_{F=f(x)-f(y),\;f\ge0} \left[\beta((F+v)^+)-\alpha((F+v)^-)+\hat{\varphi}(-f)\right],\] where \[\mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta):= \{\mu\in \mathcal{M}(\mathcal{B}^2):\alpha\le\mu\le\beta, \;\partial\mu\le\varphi\}.\]
Proof. Necessity. If such a flow \(\mu\) exists, then for any potential \(F\) and any measurable \(g\) we have the elementary bounds \[\alpha(g^+)-\beta(g^-)\;\le\;\mu(g)\;\le\;\beta(g^+)-\alpha(g^-),\] valid whenever \(\alpha\le \mu\le \beta\). With \(g=F+v\) and using 8 we have \[\beta((F+v)^+)-\alpha((F+v)^-)\;\geq \;\mu(F+v) \;=\;\mu(F)+\mu(v) \;\geq \;c -\hat{\varphi}(-f),\] giving the right-hand inequality in ?? . Similarly, \[\alpha((F+v)^+)-\beta((F+v)^-)\;\leq \;\mu(F+v)\;=\;\mu(F)+\mu(v)\;\leq \;c+\hat{\varphi}(f),\] which yields the left-hand inequality.
Sufficiency. Let \(\mathcal{S}\) be the set of all submodular flows, \(\mathcal{H}=\{\mu \in \mathcal{M}(\mathcal{B}^2): \mu(v)=c\}\) and \(\mathcal{X}=\{\mu \in \mathcal{M}(\mathcal{B}^2): \alpha\le \mu\le \beta\}\). For \(\epsilon>0\), let \(\mathcal{S}_\epsilon=B_\epsilon(\mathcal{S})\), \(\mathcal{H}_\epsilon=B_\epsilon(\mathcal{H})\) and \(\mathcal{X}_\epsilon=B_\epsilon(\mathcal{X})\) to be the \(\epsilon\)-ball in the total variation norm. We claim that \[\mathcal{S}_\epsilon\cap \mathcal{H}_\epsilon\cap \mathcal{X}_\epsilon\neq \emptyset\] for any \(\epsilon>0\).
Suppose, for contradiction, that \(\mathcal{S}_\epsilon\cap \mathcal{H}_\epsilon\cap \mathcal{X}_\epsilon=\emptyset\) for some \(\epsilon>0\). By 2 there exist bounded linear functionals \(\mathcal{L}_i\) on \(\mathcal{M}(\mathcal{B}^2)\) and \(a_i\in \mathbb{R}\) (\(i=1,2,3\)) such that \[\mathcal{L}_1+\mathcal{L}_2+\mathcal{L}_3=0,\;a_1+a_2+a_3=0,\;\mathcal{L}_i(\mu_i)\geq a_i,\;\sum_{i=1}^3\mathcal{L}_i(\mu_i)>0,\;\mu_1\in \mathcal{S},\; \mu_2\in\mathcal{H},\; \mu_3\in \mathcal{X}.\] Note that for any submodular flow \(\mu\) and circulation \(\nu\), we have \(\mu+a\nu\) is a submodular flow for any \(a\in\mathbb{R}\). Thus \(\mathcal{L}_1(\mu)+a\mathcal{L}_1(\nu)=\mathcal{L}_1(\mu+a\nu)\geq a_1\) for any \(a\in \mathbb{R}\) and so \(\mathcal{L}_1(\nu)=0\) for any circulation \(\nu\).
By 4 there exists some \(\lambda_\varphi\in \mathcal{M}_+(\mathcal{B})\) such that for any \(\mu\in \mathop{\mathrm{\mathsf{bmm}}}(\varphi)\), \(\mu\ll \lambda_\varphi\). Let \(\nu_0=\lambda_\varphi\otimes \lambda_\varphi+|\alpha|+|\beta|\). By 3 there exists a potential \(F(x,y)=f(x)-f(y)\) with \(0\leq f< C\) such that \(\mathcal{L}_1(\mu)=\mu(F)\) for all \(\mu \in \mathcal{M}(\mathcal{B}^2)\) with \(\mu\ll \nu_0\). By 8 there exists \(\nu_1,\nu_2\in\mathcal{M}_+(\mathcal{B}^2)\) such that \(\nu_1,\nu_2\ll \nu_0\), \(\nu_1(F)= -\hat{\varphi}(-f)\) and \(\nu_2(-F)=\hat{\varphi}(-f)\). Similarly, since \(\mathcal{H}\) is a hyperplane and \(\mathcal{L}_2(\mathcal{H})\geq a_2\), there exists \(b\in \mathbb{R}\) such that for any \(\mu\in \mathcal{M}(\mathcal{B}^2)\) we have \(\mathcal{L}_2(\mu)=b\mu(v)\). Then \(\mathcal{L}_3(\mu)=-\mu(F)-b\mu (v)=-\mu(F+bv)\). By the above discussion, for any \(\mu_1\in \mathcal{S},\; \mu_2\in\mathcal{H},\; \mu_3\in \mathcal{X}\) with \(\mu_1\ll\nu_0\) we have \[0=a_1+a_2+a_3<\mu_1(F)+bc-\mu_3(F+bv),\] and thus \[\beta((F+bv)^+)-\alpha((F+bv)^-)<\mu_1(F)+bc.\] If \(b\ne0\), divide the separating inequality by \(|b|\) and replace \(F\) by \(F/|b|\). Thus it suffices to consider \(b=1\) and \(b=-1\). The case \(b=0\) is treated separately.
If \(b=1\), let \(\mu_1=\nu_1\) we have \[\beta((F+v)^+)-\alpha((F+v)^-)<c-\hat{\varphi}(-f),\] contradicting the right-hand side of ?? .
If \(b=-1\), let \(\mu_1=\nu_2\) we have \[\alpha((-F+v)^+)-\beta((-F+v)^-)>c+\hat{\varphi}(-f),\] contradicting the left-hand side of ?? .
If \(b=0\), let \(\mu_1=\nu_1\) we have \[\beta(F^+)-\alpha(F^-)<-\hat{\varphi}(-f).\] Let \(B_t=\{C-f\geq t\}\). Then \(\hat{\varphi}(-f)=\hat{\varphi}(C-f)=\int_0^C\varphi(B_t)\;\mathrm{d} t\). By 5 and Fubini’s Theorem, \[\begin{align} -\hat{\varphi}(-f)&=-\int_0^C\varphi(B_t)\;\mathrm{d} t\leq \int_0^C \big(\beta(B_t^c\times B_t)-\alpha(B_t\times B_t^c)\big)\;\mathrm{d} t\\ &=\int_0^C \int_{B_t^c\times B_t} 1 \;\text{d}\beta(x,y) - \int_{B_t\times B_t^c} 1 \;\text{d}\alpha(x,y) \; \mathrm{d} t\\ &=\int_{\{(x,y)\;:\; f(x)>f(y)\}} \int_{f(y)}^{f(x)} 1 \; \mathrm{d} t\;\text{d}\beta(x,y)-\int_{\{(x,y)\;:\; f(x)<f(y)\}} \int_{f(x)}^{f(y)} 1 \; \mathrm{d} t\;\text{d}\alpha(x,y)\\ &=\beta(F^+)-\alpha(F^-), \end{align}\] a contradiction.
Therefore \(\mathcal{S}_\epsilon\cap \mathcal{H}_\epsilon\cap \mathcal{X}_\epsilon\neq \emptyset\) for every \(\epsilon>0\).
For each \(n\ge 1\), choose \[\xi_n\in \mathcal{S}_{2^{-n}}\cap \mathcal{H}_{2^{-n}}\cap \mathcal{X}_{2^{-n}}.\] By the definition of the \(2^{-n}\)-neighborhoods, we may choose \(\mu_n\in \mathcal{S}\), \(\eta_n\in \mathcal{H}\), and \(\omega_n\in \mathcal{X}\) such that \[\|\xi_n-\mu_n\|<2^{-n}, \|\xi_n-\eta_n\|<2^{-n}, \|\xi_n-\omega_n\|<2^{-n}.\] Hence \(\|\mu_n-\omega_n\|<2^{1-n}\) and \(\|\eta_n-\omega_n\|<2^{1-n}\).
Since \(\omega_n\in\mathcal{X}\), we have \(\alpha\le \omega_n\le \beta\) for every \(n\). Therefore \(|\omega_n|\le 2|\alpha|+|\beta|\) for every \(n\). By 1, after passing to a subsequence, there exists \(\omega\in\mathcal{M}(\mathcal{B}^2)\) such that \(\omega_n(U)\to \omega(U)\) for every \(U\in\mathcal{B}^2\).
We claim that the same subsequence satisfies \(\mu_n(U)\to \omega(U)\) and \(\eta_n(U)\to \omega(U)\) for every \(U\in\mathcal{B}^2\). Indeed, for every \(U\in\mathcal{B}^2\), \[|\mu_n(U)-\omega(U)| \le |\mu_n(U)-\omega_n(U)|+|\omega_n(U)-\omega(U)| \le \|\mu_n-\omega_n\|+|\omega_n(U)-\omega(U)|\to 0,\] and similarly \(\eta_n(U)\to\omega(U)\).
We now verify that \(\omega\in \mathcal{S}\cap \mathcal{H}\cap \mathcal{X}\). Since \(\omega_n\in\mathcal{X}\), for every \(U\in\mathcal{B}^2\) we have \(\alpha(U)\le \omega_n(U)\le \beta(U)\). Passing to the limit gives \(\alpha(U)\le \omega(U)\le \beta(U)\) for all \(U\in\mathcal{B}^2\), so \(\omega\in\mathcal{X}\). Since each \(\eta_n\in\mathcal{H}\), we have \(\eta_n(v)=c\). Since \(v\) is bounded and measurable and \(\eta_n\to\omega\) setwise, it follows that \(\omega(v)=\lim_{n\to\infty}\eta_n(v)=c\). Hence \(\omega\in\mathcal{H}\). Since each \(\mu_n\in\mathcal{S}\), for every \(A\in\mathcal{B}\), we have \[\partial\mu_n(A)=\mu_n(A\times A^c)-\mu_n(A^c\times A)\le \varphi(A).\] Passing to the limit, using the setwise convergence of \(\mu_n\) to \(\omega\) on the sets \(A\times A^c\) and \(A^c\times A\), we obtain \(\partial\omega(A)\le \varphi(A)\) for all \(A\in\mathcal{B}\). Thus \(\omega\in\mathcal{S}\).
Therefore \(\omega\in \mathcal{S}\cap \mathcal{H}\cap \mathcal{X}\), so \(\omega\) is a feasible submodular flow with cost \(c\). ◻
Let \(\Lambda_0:=|\alpha|+|\beta|\). Recall that \[\mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta):= \{\mu\in \mathcal{M}(\mathcal{B}^2):\alpha\le\mu\le\beta, \;\partial\mu\le\varphi\}.\] If \(\mu\in\mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)\), then \(\alpha\le\mu\le\beta\), and hence \(|\mu|\le \Lambda_0\). Thus every feasible flow is absolutely continuous with respect to \(\Lambda_0\). Identifying such a measure \(\mu\) with its Radon–Nikodým derivative \(f_\mu:=\frac{\mathrm d\mu}{\mathrm d\Lambda_0}\), the set \[K_{\Lambda_0}:= \{\mu\in M(\mathcal{B}^2): |\mu|\le\Lambda_0\}\] is identified with the closed unit ball of \(L^\infty(\Lambda_0)\).
We equip \(K_{\Lambda_0}\) with the weak-* topology \(\sigma(L^\infty(\Lambda_0),L^1(\Lambda_0))\), that is, the topology in which \(f_i\to f\) if and only if \[\int f_i h\,d\Lambda_0\to \int f h\,d\Lambda_0 \qquad\text{for every }h\in L^1(\Lambda_0).\] By the Banach–Alaoglu theorem, \(K_{\Lambda_0}\) is compact in this topology. On \(K_{\Lambda_0}\), this topology agrees with the topology of setwise convergence of measures. Indeed, indicators of measurable sets belong to \(L^1(\Lambda_0)\), and conversely simple functions are dense in \(L^1(\Lambda_0)\), while all densities in \(K_{\Lambda_0}\) are uniformly bounded by \(1\).
The capacity constraints are weak-* closed, since they are equivalent to \[\alpha(U)\le\mu(U)\le\beta(U), \qquad U\in\mathcal{B}^2,\] and each map \(\mu\mapsto\mu(U)\) is weak-* continuous. Similarly, for every \(X\in\mathcal{B}\), the boundary functional \[\mu\mapsto\partial\mu(X) = \mu(X\times X^c)-\mu(X^c\times X)\] is weak-* continuous. Hence the constraints \[\partial\mu(X)\le\varphi(X),\qquad X\in\mathcal{B},\] define a weak-* closed subset of \(K_{\Lambda_0}\).
Consequently, \(\mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)\) is a weak-* compact convex set. By the Krein–Milman theorem, it is the weak-* closed convex hull of its extreme points.
We now characterize the extreme points. Recall that a point \(x\) in a convex set \(C\) is an extreme point if there is no two distinct points \(y_1,y_2\in C\) such that \(x=\frac{1}{2}( y_1+y_2)\).
We begin with some basic calculation rules. Let \(\Lambda=\Lambda_0+\Lambda_0^*\), then any flow \(\mu\) with \(\alpha\le \mu\le \beta\) is absolutely continuous with respect to \(\Lambda\). We denote by \(f_\gamma\colon J\times J\to \mathbb{R}\) the Radon–Nikodým derivative for any signed measure \(\gamma\ll \Lambda\). The function \(f_\gamma^*\colon J\times J\to \mathbb{R}\), \(f_\gamma^*(x,y)=f_\gamma(y,x)\) is called the transpose of \(f_\gamma\). Note that \(f^*_\gamma=f_{\gamma^*}\). For any two functions \(f,g\colon J\times J\to \mathbb{R}\), let \(f\vee g=\max\{f,g\}\), \(f\wedge g=\min\{f,g\}\), \(f_+=f\vee 0\), \(f_-=f\wedge 0\) and \(f|_E=f\mathbf{1}_E\) for any \(E\in\mathcal{B}^2\). Here \(\mathbf{1}_E\) is the indicator function of subset \(E\). If the integral makes sense, we define the measure induced by \(f\) to be \[f\Lambda \colon \mathcal{B}^2\to\mathbb{R},\; f\Lambda(X)=\int_X f(x,y)\,\mathrm{d}\Lambda.\] Functions are identified when they agree \(\Lambda\)-almost everywhere.
The following proposition is immediate from the Radon–Nikodým representation with respect to the common dominating measure \(\Lambda\).
Proposition 1. For any two functions \(f,g\colon J\times J\to \mathbb{R}\), flows \(\gamma,\gamma_1,\gamma_2\) and measurable \(E,E_1,E_2\), the following calculation rules hold:
\(\partial \gamma ^{*}=-\partial \gamma\);
if \(\gamma,\gamma_1,\gamma_2\ll \Lambda\), then \(f_\gamma\Lambda=\gamma\), \((f_{\gamma_1}\vee f_{\gamma_2} )\Lambda=\gamma_1\vee\gamma_2\) and \((f_{\gamma_1}\wedge f_{\gamma_2}) \Lambda=\gamma_1\wedge\gamma_2\);
\((f\wedge g)^*=f^*\wedge g^*\) and \((\gamma_{1}\wedge \gamma_{2})^{*}=\gamma_{1}^{*}\wedge \gamma_{2}^{*}\);
\((f-g)_+=f-f\wedge g\) and \((\gamma_{1}-\gamma_{2})_{+}=\gamma_{1}-\gamma_{1}\wedge \gamma_{2}\);
\((f_+)^*=(f^*)_+\) and \((\gamma _{+})^{*}=(\gamma ^{*})_{+}\);
\(f_\gamma=f_\gamma|_E\) if \(f|_{E^c}=0\), and \(\gamma=\gamma|_{E}\) if \(\gamma\) is supported on \(E\);
If \(J \times J =E_{1}\sqcup E_{2}\), then \[f\wedge g=f|_{E_1}\wedge g|_{E_1}+f|_{E_2}\wedge g|_{E_2}\quad \textrm{ and } \quad\gamma_{1}\wedge \gamma_{2}=\gamma_{1}|_{E_{1}}\wedge \gamma_{2}|_{E_{1}}+\gamma_{1}|_{E_{2}}\wedge \gamma_{2}|_{E_{2}}.\]
To start, we consider particular feasible flows with given marginals. Given two measures \(\sigma,\tau\in\mathcal{M}_+(\mathcal{B})\) with \(\sigma(J)=\tau(J)\), the set of all feasible \(\sigma\)-\(\tau\) flows is denoted by \[\mathcal{F}=\mathcal{F}(J,\mathcal{B},\alpha,\beta,\sigma,\tau) \;:=\;\{\mu\in\mathcal{M}(\mathcal{B}^2):\;\alpha\le \mu\le \beta,\;\mu^1-\mu^2=\sigma-\tau\}.\] Similar to \(\mathcal{F}_\varphi\), the set \(\mathcal{F}\) is a weak-* closed convex subset of \(\mathcal{M}(\mathcal{B}^2)\). A flow \(\mu\in \mathcal{F}\) is an extreme point of \(\mathcal{F}\) if and only if there is no non-zero flow \(\gamma\in \mathcal{M}(\mathcal{B}^2)\) such that \(\mu\pm \gamma\in\mathcal{F}\). Note that the condition \(\mu \pm \gamma \in \mathcal{F}\) requires \(\gamma\) to be a circulation. The capacity constraints \(\alpha \le \mu \pm \gamma \le \beta\) are equivalent to \[\pm\gamma \le \mu - \alpha\quad\text{ and }\quad \pm\gamma \le \beta - \mu.\] Thus we define \[\eta=\eta(\mu;\alpha,\beta):=(\beta-\mu)\wedge(\mu-\alpha).\] Then \(\mu\) is an extreme point of \(\mathcal{F}\) if and only if there is no non-zero circulation \(\gamma\) such that \(-\eta\leq \gamma\leq \eta.\)
As in the finite case, we can transform this condition concerning signed measures to concern only measures with a generalized notion of residual graphs as below.
A nonnegative flow \(\mu\) is called trivial if \(\mu=\mu\wedge\mu^*\) and is called reduced if \(\mu\wedge\mu^*=0\).
By Hahn decomposition we have the following lemma.
Lemma 9. If \(\mu\) is a reduced flow, there exists \(E\in \mathcal{B}^2\) such that \(E\cap E^*=\emptyset\) and \(\mu\) is supported on \(E\).
Proof. Since \(\mu\wedge\mu^*=0\), there exists a Borel partition \(J\times J=E_1\sqcup E_2\) such that \(\mu(E_2)=\mu^*(E_1)=0\). Then \[\mu(E_1\setminus E_1^*)=\mu(J\times J)-\mu(E_1^*)=\mu(J\times J)-\mu^*(E_1)=\mu(J\times J),\] so \(\mu\) is supported on \(E:= E_1\setminus E_1^*\), and clearly \(E\cap E^*=\emptyset\). ◻
Given a flow \(\mu \in \mathcal{F}\), the measurable residual graph of \(\mu\) is defined as \[R=R(\mu;\alpha,\beta):= \eta(\mu;\alpha,\beta)+\eta(\mu;\alpha,\beta)^*.\] The trivial circulation graph of \(\mu\) is defined as \[T=T(\mu;\alpha,\beta):=\eta(\mu;\alpha,\beta)\wedge \eta(\mu;\alpha,\beta)^*.\]
As the classical residual graph, the measure \(R\) describes how much a given flow can be adjusted in either direction—increasing (\(\eta\)) or decreasing (\(\eta^*\)); while \(T\) captures flows whose weight coincide on every pair of arcs that has opposite direction, which vanishes for oriented graphs. If \(J\) is finite, \(f_R\) is the weight function of the residual graph, and a reduced circulation in \(R\) corresponds to some cycles with positive weight in the residual graph. Further, \(T\) corresponds to cycles of length 2 with positive weight in the residual graph.
Lemma 10. A flow \(\mu\in\mathcal{F}\) is an extreme point of \(\mathcal{F}\) if and only if \(T=0\) and there is no reduced circulation \(\gamma\) such that \(0< \gamma\leq R\).
Proof. First assume \(\mu\) is an extreme point of \(\mathcal{F}\). Since \(T=T^*\), 1 [property1] gives \(2\partial T=\partial T+\partial T^*=0\), so \(T\) is a circulation. Assume \(T\neq 0\). Recall that \(\eta = (\beta-\mu)\wedge(\mu-\alpha) \ge 0\) since \(\alpha \le \mu \le \beta\). By definition, \(T = \eta \wedge \eta^*\), which implies \(0 \le T \le \eta\), and thus \(-\eta \le \pm T \le \eta\). Because \(\eta \le \beta - \mu\) and \(\eta \le \mu - \alpha\), the bounds \(-\eta \le \pm T \le \eta\) guarantee the capacity constraints \(\alpha \le \mu \pm T \le \beta\). Furthermore, \(T\) is a circulation, contradicting that \(\mu\) is extreme. Thus \(T = \eta \wedge \eta^* = 0\) and \(\eta\) is a reduced flow.
Suppose there is a nonzero reduced circulation \(\gamma\) such that \(0< \gamma\leq R\). Let \[f_1:=f_\gamma\wedge f_\eta, \qquad f_2:=f_{\gamma}\wedge f_{\eta^*}.\] Then \(f_1\Lambda\leq \eta\) and \(f_2\Lambda \leq \eta^*\). Since \(\eta\) is reduced, \[f_\gamma=f_\gamma\wedge f_R=(f_\gamma\wedge f_R)|_{\{f_\eta>0\}}+(f_\gamma\wedge f_R)|_{\{f_{\eta^*}>0\}}=f_1+f_2.\] Thus \(f_\gamma\Lambda=f_1\Lambda+f_2\Lambda\). Define \[\mu_1:=\mu+f_1\Lambda-f_2^*\Lambda,\qquad \mu_2:=\mu-f_1\Lambda+f_2^*\Lambda.\] Then \[\partial\mu_1=\partial\mu_2=\partial \mu+\partial (f_1\Lambda)+\partial (f_2\Lambda)=\partial\mu +\partial \gamma=\partial\mu,\] and similarly \(\partial\mu_2=\partial\mu\). Thus \(\mu_1,\mu_2\in\mathcal{F}\) and \(\mu=(\mu_1+ \mu_2)/2\). Extremality gives \(\mu_1=\mu_2\), hence \(f_1=f_2^*\), which implies \[\gamma\wedge\gamma^*=(f_1\Lambda+f_2\Lambda)\wedge(f_1^*\Lambda+f_2^*\Lambda)=\gamma,\] contradicting that \(\gamma\) is reduced.
Now we assume \(T=0\) and there is no nonzero reduced circulation \(\gamma\) such that \(0\leq \gamma\leq R\). Suppose, for contradiction, that \(\mu\) is not an extreme point of \(\mathcal{F}\). Then there exist distinct flows \(\mu_1,\mu_2\in\mathcal{F}\) such that \(\mu=\dfrac{\mu_1+\mu_2}{2}\), which implies \(\mu_1-\mu = \mu-\mu_2\).
Let \(\delta_1:=(\mu_1-\mu)_+\) and \(\delta_2:=(\mu-\mu_1)_+\) be the positive and negative variations of the signed measure \(\mu_1-\mu\), meaning \(\mu_1-\mu = \delta_1-\delta_2\). Because \(\mu_1 \le \beta\) and \(\mu_2 \ge \alpha\), we can bound \(\delta_1\) simultaneously in two ways: \[\delta_1 = (\mu_1-\mu)_+ \le (\beta-\mu)_+ = \beta-\mu \quad \text{and} \quad \delta_1 = (\mu-\mu_2)_+ \le (\mu-\alpha)_+ = \mu-\alpha.\] Therefore, \(\delta_1 \le (\beta-\mu)\wedge(\mu-\alpha) = \eta\). Taking the transpose yields \(\delta_1^* \le \eta^*\). Thus, \(\delta_1 \wedge \delta_1^* \le \eta \wedge \eta^* = T\). Since \(T=0\) by our assumption, we have \(\delta_1 \wedge \delta_1^* = 0\), meaning \(\delta_1\) is a reduced flow. By symmetry, \(\delta_2\leq \eta\) and \(\delta_2\) is also a reduced flow.
By the Hahn decomposition theorem, \(\delta_1\) and \(\delta_2\) are mutually singular and there exist disjoint Borel sets \(E_1, E_2 \subseteq J \times J\) such that \(\delta_i\) is supported on \(E_i\) for \(i=1,2\). Since \(\delta_1\) and \(\delta_2\) are reduced, by 9 we can additionally require \(E_1 \cap E_1^* = \emptyset\) and \(E_2 \cap E_2^* = \emptyset\).
We now construct a new flow \(\delta := \delta_1 + \delta_2^*\). First, since \(\mu_1, \mu \in \mathcal{F}\) share identical marginals, we have \(\partial(\mu_1 - \mu) = \partial\delta_1 - \partial\delta_2 = 0\). By 1 [property1], \(\partial\delta = \partial\delta_1 + \partial\delta_2^* = \partial\delta_1 - \partial\delta_2 = 0\), meaning \(\delta\) is a circulation. Second, since \(\delta_1 \le \eta\) and \(\delta_2 \le \eta\) (which implies \(\delta_2^* \le \eta^*\)), we inherently have \(0 \le \delta \le \eta + \eta^* = R\). Finally, we verify that \(\delta\) is reduced. The flow \(\delta\) is supported on \(E_1 \cup E_2^*\), and its transpose \(\delta^*\) is supported on \(E_1^* \cup E_2\). By our assumption, \[E_1 \cap E_1^* = E_2 \cap E_2^* = E_1 \cap E_2 = (E_2^* \cap E_1^*) = (E_1 \cap E_2)^* = \emptyset,\] and thus the intersection of their supports \((E_1 \cup E_2^*) \cap (E_1^* \cup E_2) = \emptyset.\)
Therefore, \(\delta \wedge \delta^* = 0\), meaning \(\delta\) is a nonzero reduced circulation satisfying \(0 \le \delta \le R\), a contradiction. ◻
Now we are ready to give a characterization of extreme submodular flows. By considering common basic minorizing measures, we can transform the submodular flow problem to a flow problem with fixed marginals.
Theorem 7. For any \(\mu\in \mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)\), let \(\eta=\eta(\mu;\alpha,\beta)\), \(R=R(\mu;\alpha,\beta)\) and \(T=T(\mu;\alpha,\beta)\). Then \(\mu\) is an extreme point of \(\mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)\) if and only if the following two statements hold:
\(\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{-\eta,\eta})\cap\mathop{\mathrm{\mathsf{bmm}}}(\varphi-\partial\mu)\cap \mathop{\mathrm{\mathsf{bmm}}}((\varphi-\partial\mu)^c)=\{0\}\);
\(T=0\), and there is no reduced circulation \(\gamma\) such that \(0< \gamma\leq R\).
Here \((\varphi-\partial\mu)^c(X) := (\varphi-\partial\mu)(X^c)\) for any \(X\in\mathcal{B}\), a submodular set function whose value for \(\emptyset\) is 0.
Proof. For any \(\mu\in \mathcal{F}_\varphi(J,\mathcal{B},\alpha,\beta)\), \(\mu\) is an extreme point if and only if there is no \(\gamma\in\mathcal{M}(\mathcal{B}^2)\) such that \(\alpha\leq \mu\pm\gamma\leq \beta\) and \(\partial\mu\pm\partial\gamma\leq \varphi\). The first condition is equivalent to say that \(-\eta\leq \gamma\leq \eta,\) and the second condition is equivalent to say that \(-(\varphi-\partial\mu) \leq \partial\gamma\leq \varphi-\partial\mu.\) Let \[\psi:=\varphi-\partial\mu, \qquad \psi^c(X):=\psi(X^c).\] Then both \(\psi\) and \(\psi^c\) are bounded continuous submodular set functions.
For any \(X\in\mathcal{B}\), since \(\partial\gamma(X)+\partial\gamma(X^c)=0\) and \[\partial\gamma(X)+\psi(X)=\psi^c(X^c)-\partial\gamma(X^c).\] Thus the second condition is equivalent to the fact that \(\partial\gamma\in \mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi^c)\).
Assume \(\mu\) is an extreme point. By 6, we have \[\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{-\eta,\eta})=\{\partial \gamma \;:\;\gamma\in\mathcal{M}(\mathcal{B}^2),\; -\eta\leq \gamma\leq \eta\}.\] Then \(\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{-\eta,\eta})\cap\mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi^c)=\{0\}\), or otherwise there exists a nonzero flow \(\gamma\) such that \(-\eta\leq \gamma\leq \eta\) and \(\partial\gamma\in \mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi^c)\), a contradiction. Further, since \[\mathcal{F}:=\mathcal{F}(J,\mathcal{B},\alpha,\beta,(\partial\mu)_+,(\partial\mu)_-)\subseteq \mathcal{F}_\varphi,\] \(\mu\) is also an extreme point of \(\mathcal{F}\). By 10, condition [cond2] in the theorem holds.
Conversely, assume the two conditions in the theorem hold and \(\mu\) is not an extreme point. By the previous discussion, there exists a nonzero flow \(\gamma\) such that \(-\eta\leq \gamma\leq \eta\) and \(-(\varphi-\partial\mu) \leq \partial\gamma\leq \varphi-\partial\mu\). Since \(\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{-\eta,\eta})\cap\mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap \mathop{\mathrm{\mathsf{bmm}}}(\psi^c)=\{0\}\), we have \(\partial\gamma=0\) and thus \(\mu\pm\gamma\in\mathcal{F}\). However, by 10 and condition [cond2], \(\mu\) is an extreme point of \(\mathcal{F}\) and thus \(\gamma=0\), a contradiction. ◻
In classical network flow theory, if the lower bound of edge capacity is 0, it is standard to consider net flows in order to eliminate transport redundancies. On a directed graph, simultaneous flows in opposite directions between two adjacent nodes (i.e., trivial \(2\)-cycles) do not contribute to the flow while increasing the cost. To remove this redundancy, one typically subtracts the weight on opposite edges simultaneously until one direction become zero. We extend this notion to the measurable setting as follows. Fix a network system \((J,\mathcal{B},0,\beta)\).
Definition 8. The reduction map is defined as \[P\colon \mathcal{M}_+(\mathcal{B}^2)\to \mathcal{M}_+(\mathcal{B}^2), \qquad P(\mu):=\mu-\mu\wedge \mu^*=(\mu-\mu^*)_+.\] We define \(\mu\sim\nu\) if \(P(\mu)=P(\nu)\), and then \(\sim\) is an equivalence relation on \(\mathcal{M}_+(\mathcal{B}^2)\). Notice that \[P(\mu) - P(\mu)^* = (\mu-\mu^*)_+ - (\mu-\mu^*)_- = \mu - \mu^*.\] Since \(P(\mu)\) and \(P(\mu)^*\) are mutually singular, \(P(\mu) = P(\nu)\) if and only if \(\mu - \mu^* = \nu - \nu^*\). Thus the equivalence relation \(\sim\) is precisely the equivalence modulo the kernel of the linear operator \[L(\mu) := \mu - \mu^*.\] The equivalence class containing \(\mu\) is denoted by \([\mu]\). Note that \([P(\mu)]=[\mu]\).
The flow \(P(\mu)\) is called the reduced flow of \(\mu\), serving as the canonical non-negative representative of its equivalence class. For fixed \(\sigma,\tau\in\mathcal{M}_+(\mathcal{B})\) with \(\sigma(J)=\tau(J)\), we denote all reduced feasible \(\sigma\)-\(\tau\) flows by the quotient space: \[\widetilde{\mathcal{F}}= \widetilde{\mathcal{F}}(J,\mathcal{B},\beta,\sigma,\tau):=\mathcal{F}(J,\mathcal{B},0,\beta,\sigma,\tau)/\sim.\]
Because \(\sim\) is induced by the linear map \(L\), the quotient space \(\widetilde{\mathcal{F}}\) is affinely isomorphic to the image \(L(\mathcal{F})\), a convex subset of signed measures. Through this isomorphism, \(\widetilde{\mathcal{F}}\) naturally inherits a rigorous convex structure, where convex combinations are defined by \[c[\mu_1] + (1-c)[\mu_2] := [c\mu_1 + (1-c)\mu_2],\qquad 0 \le c \le 1,\] independent of the choice of representatives. We equip the quotient space \(\widetilde{\mathcal{F}}\) with the metric induced by the total variation norm. That is, \[d( [\mu],[\nu] )= \inf\{ \| \mu_1-\nu_1 \| \;:\; [\mu_1]= [\mu],\; [\nu_1]= [\nu] \} .\] Then \(\widetilde{\mathcal{F}}\) is a Banach space and it is easy to see that \(d( [\mu],[\nu] )=\|P(\mu)-P(\nu) \|\).
We give a characterization of extreme flows in \(\widetilde{\mathcal{F}}\) as follows. Given \([\mu]\in \widetilde{\mathcal{F}}\), define the residual graph as \[R=R([\mu];\beta):= (\beta - P(\mu) + P(\mu)^*) \wedge (\beta^* - P(\mu)^* + P(\mu)).\]
Lemma 11. For any \([\mu]\in \widetilde{\mathcal{F}}(J,\mathcal{B},\beta,\sigma,\tau)\), \([\mu]\) is an extreme point of \(\widetilde{\mathcal{F}}(J,\mathcal{B},\beta,\sigma,\tau)\) if and only if there is no reduced circulation \(\gamma\) such that \(0<\gamma\le R([\mu];\beta).\)
Proof. Let \(\mathcal{F}:=\mathcal{F}(J,\mathcal{B},0,\beta,\sigma,\tau)\). Consider the linear map \(L:\mathcal{M}(\mathcal{B}^2)\to\mathcal{M}(\mathcal{B}^2)\) defined by \(L(\theta):=\theta-\theta^*\). By the definition of the equivalence relation, \([\theta_1]=[\theta_2]\) if and only if \(L(\theta_1)=L(\theta_2)\). Hence \(\widetilde{\mathcal{F}}\) is affinely isomorphic to \(L(\mathcal{F})\). Let \[\mathcal{G}:=\{\nu\in\mathcal{M}(\mathcal{B}^2):\nu^*=-\nu,\;\partial\nu=2(\sigma-\tau),\;\nu_+\le\beta\}.\] We claim that \(L(\mathcal{F})=\mathcal{G}\). Indeed, if \(\theta\in\mathcal{F}\), then \(L(\theta)^*=-L(\theta)\), \(\partial L(\theta)=\partial(\theta-\theta^*)=2\partial\theta=2(\sigma-\tau)\), and \(L(\theta)_+=(\theta-\theta^*)_+=P(\theta)\le\theta\le\beta\). Hence \(L(\theta)\in\mathcal{G}\). Conversely, if \(\nu\in\mathcal{G}\), then \(\nu^*=-\nu\) and \(v_-=(v_+)^*\). Thus \(\nu=\nu_+-(\nu_+)^*\) and \(\partial\nu=2\partial\nu_+\). Since \(\partial\nu=2(\sigma-\tau)\), we get \(\partial\nu_+=\sigma-\tau\). Together with \(0\le\nu_+\le\beta\), this gives \(\nu_+\in\mathcal{F}\), and \(L(\nu_+)=\nu\). Therefore \(L(\mathcal{F})=\mathcal{G}\).
It follows that \([\mu]\) is extreme in \(\widetilde{\mathcal{F}}\) if and only if \(\nu:=L(\mu)\) is extreme in \(\mathcal{G}\). Replacing \(\mu\) by its reduced representative \(P(\mu)\), we may assume that \(\mu=P(\mu)\). Then \(\nu=\mu-\mu^*\), \(\nu_+=\mu\), and \[R=R([\mu];\beta) = (\beta-\mu+\mu^*)\wedge(\beta^*-\mu^*+\mu) = (\beta-\nu)\wedge(\beta^*+\nu).\] Note that \(\nu\) is not extreme in \(\mathcal{G}\) if and only if there exists a nonzero signed measure \(\gamma\) such that \(\nu\pm\gamma\in\mathcal{G}\). This is equivalent to \[\gamma^*=-\gamma, \quad\partial\gamma=0,\quad (\nu\pm\gamma)_+\le\beta.\] Since \(\beta\ge0\), the inequalities \((\nu\pm\gamma)_+\le\beta\) are equivalent to \(\nu\pm\gamma\le\beta\), and hence to \(\gamma\le\beta-\nu\) and \(-\gamma\le\beta-\nu\). Taking the transpose of the second inequality gives \(\gamma\le\beta^*+\nu\). Thus \([\mu]\) is extreme in \(\widetilde{\mathcal{F}}\) if and only if there exists no nonzero signed measure \(\gamma\) such that \(\gamma^*=-\gamma\), \(\partial\gamma=0\) and \(\gamma\le(\beta-\nu)\wedge(\beta^*+\nu)=R\).
Assume \([\mu]\) is not extreme, pick such \(\gamma\) and set \(\rho:=\gamma_+\). Since \(\gamma^*=-\gamma\), we have \(\gamma=\rho-\rho^*\) and \(\rho\) is reduced. Moreover, \(\partial\gamma=\partial(\rho-\rho^*)=2\partial\rho\), so \(\rho\) is a reduced circulation. Since both \(\beta-\nu\) and \(\beta^*+\nu\) are nonnegative measures, the inequalities \(\gamma\le\beta-\nu\) and \(\gamma\le\beta^*+\nu\) imply \(\rho=\gamma_+\le(\beta-\nu)\wedge(\beta^*+\nu)=R\). Also \(\gamma\ne0\) implies \(\rho\ne0\), a contradiction.
Conversely, suppose that there exists a reduced circulation \(\rho\) such that \(0<\rho\le R\). Let \(\gamma:=\rho-\rho^*\). Then \(\gamma^*=-\gamma\), \(\partial\gamma=2\partial\rho=0\), and \(\gamma\ne0\). Since \(\rho\le R\), taking transpose gives \(\rho^*\le R\). Hence \[\gamma=\rho-\rho^*\le\rho\le\beta-\nu \quad \text{ and }\quad -\gamma=\rho^*-\rho\le\rho^*\le\beta-\nu.\] Therefore \(\nu\pm\gamma\le\beta\), and since \(\beta\ge0\), this implies \((\nu\pm\gamma)_+\le\beta\). Together with \(\gamma^*=-\gamma\) and \(\partial\gamma=0\), we get \(\nu\pm\gamma\in\mathcal{G}\), Thus \(\nu\) is not an extreme point of \(\mathcal{G}\), and consequently \([\mu]\) is not an extreme point of \(\widetilde{\mathcal{F}}\). This proves the theorem. ◻
Since deleting a trivial flow from a flow \(\mu\) does not change its boundary, the same reduction procedure applies to submodular flows with zero lower capacity. Fix a submodular network system \((J,\mathcal{B},0,\beta,\varphi)\) and write \[\mathcal{F}_\varphi(J,\mathcal{B},\beta) := \{\mu\in\mathcal{M}_+(\mathcal{B}^2):0\le\mu\le\beta,\;\partial\mu\le\varphi\} \quad \text{ and } \quad \widetilde{\mathcal{F}}_\varphi(J,\mathcal{B},\beta) := \mathcal{F}_\varphi(J,\mathcal{B},\beta)/{\sim}.\]
Theorem 8. Let \([\mu]\in\widetilde{\mathcal{F}}_\varphi(J,\mathcal{B},\beta)\), and let \[\psi:=\varphi-\partial\mu, \qquad \psi^c(X):=\psi(X^c),\quad X\in\mathcal{B},\] and \(R:=R([\mu];\beta)\). Then \([\mu]\) is an extreme point of \(\widetilde{\mathcal{F}}_\varphi(J,\mathcal{B},\beta)\) if and only if the following two statements hold:
\(\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{0,R}) \cap \mathop{\mathrm{\mathsf{bmm}}}(\psi) \cap \mathop{\mathrm{\mathsf{bmm}}}(\psi^c) = \{0\};\)
there is no reduced circulation \(\rho\) such that \(0< \rho\le R.\)
Proof. We may replace \(\mu\) by its reduced representative \(P(\mu)\), since \(P(\mu)\sim\mu\) and \(\partial P(\mu)=\partial\mu\). Thus assume \(\mu=P(\mu)\), and put \(\nu:=L(\mu)=\mu-\mu^*\). Then \(\nu^*=-\nu\), \(\nu^+=\mu\), and \[R=R([\mu];\beta)=(\beta-\nu)\wedge(\beta^*+\nu).\]
Let \[\mathcal{G}_\varphi:= \{\xi\in\mathcal{M}(\mathcal{B}^2):\xi^*=-\xi,\;\xi^+\le\beta,\;\partial\xi\le 2\varphi\}.\] The map \([\theta]\mapsto L(\theta)\) identifies \(\widetilde{\mathcal{F}}_\varphi(J,\mathcal{B},\beta)\) affinely with \(\mathcal{G}_\varphi\). Indeed, if \(\theta\in\mathcal{F}_\varphi(J,\mathcal{B},\beta)\), then \(L(\theta)^*=-L(\theta)\), \(L(\theta)^+=P(\theta)\le\theta\le\beta\), and \(\partial L(\theta)=2\partial\theta\le2\varphi\). Conversely, if \(\xi\in\mathcal{G}_\varphi\), then \(\xi=\xi^+-(\xi^+)^*\), so \(L(\xi^+)=\xi\), while \(0\le\xi^+\le\beta\) and \(\partial\xi^+=\frac{1}{2}\partial\xi\le\varphi\). Hence \(\xi^+\in\mathcal{F}_\varphi(J,\mathcal{B},\beta)\).
Therefore \([\mu]\) is extreme in \(\widetilde{\mathcal{F}}_\varphi\) if and only if \(\nu\) is extreme in \(\mathcal{G}_\varphi\). The latter fails if and only if there is a nonzero \(\gamma\in\mathcal{M}(\mathcal{B}^2)\) with \(\nu\pm\gamma\in\mathcal{G}_\varphi\), equivalently, \[\gamma^*=-\gamma,\qquad \gamma\le R,\qquad \partial\gamma\le2\psi,\qquad -\partial\gamma\le2\psi .\] Since \(\partial\gamma(J)=0\), the last two inequalities are equivalently \[\frac{1}{2}\partial\gamma\in\mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap\mathop{\mathrm{\mathsf{bmm}}}(\psi^c).\]
Write \(\rho:=\gamma^+\). Since \(\gamma^*=-\gamma\), we have \(\gamma=\rho-\rho^*\), \(\rho\wedge\rho^*=0\), and \(\partial\gamma=2\partial\rho\). Moreover, as in the proof of 11, the condition \(\gamma\le R\) is equivalent to \(0<\rho\le R\). Thus \([\mu]\) is not extreme if and only if there exists a nonzero reduced flow \(\rho\) such that \[0<\rho\le R,\qquad \partial\rho\in\mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap\mathop{\mathrm{\mathsf{bmm}}}(\psi^c).\]
By 6, \[\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{0,R}) = \{\partial\rho:\rho\in\mathcal{M}(\mathcal{B}^2),\;0\le\rho\le R\}.\] Hence any such \(\rho\) with \(\partial\rho\ne0\) violates condition [rcond1], while any such \(\rho\) with \(\partial\rho=0\) is a nonzero reduced circulation and violates condition [rcond2]. Conversely, if condition [rcond1] fails, choose \(0\ne q\in\mathop{\mathrm{\mathsf{bmm}}}(\kappa_{0,R})\cap\mathop{\mathrm{\mathsf{bmm}}}(\psi)\cap\mathop{\mathrm{\mathsf{bmm}}}(\psi^c)\). By 6, there is \(0\le\theta\le R\) with \(\partial\theta=q\); then \(\gamma:=\theta-\theta^*\) is a nonzero perturbation satisfying \(\nu\pm\gamma\in\mathcal{G}_\varphi\). If condition [rcond2] fails, the same conclusion follows by taking \(\gamma:=\rho-\rho^*\) for a nonzero reduced circulation \(0<\rho\le R\). Therefore \([\mu]\) is extreme exactly when both conditions hold. ◻
As an application, we state the transshipment problem on measurable spaces as follows. Fix two standard Borel spaces \((J_1,\mathcal{B}_1)\) and \((J_2,\mathcal{B}_2)\). We always regard \(J_1\sqcup J_2\) as a disjoint union, even if the underlying sets overlap, and its \(\sigma\)-algebra is \[\mathcal{B}_1\oplus\mathcal{B}_2:=\{A_1\sqcup A_2:A_i\in\mathcal{B}_i\}.\] Given a supply measure \(\alpha\in\mathcal{M}_+(\mathcal{B}_1)\), a demand measure \(\beta\in\mathcal{M}_+(\mathcal{B}_2)\) with \(\alpha(J_1)=\beta(J_2)\), and a capacity measure \(\psi\in \mathcal{M}_+((\mathcal{B}_1\oplus \mathcal{B}_2)^2)\) supported on \(J_1\times J_2\), the tuple \((J_1,\mathcal{B}_1,J_2,\mathcal{B}_2,\alpha,\beta,\psi)\) is called a transshipment system.
Define \(\sigma_\alpha,\sigma_\beta\in\mathcal{M}_+(\mathcal{B}_1\oplus \mathcal{B}_2)\) by \[\sigma_\alpha(X)=\alpha(X\cap J_1), \qquad\sigma_\beta(X)=\beta(X\cap J_2).\] A flow \(\mu\) on \((J_1\sqcup J_2,\mathcal{B}_1\sqcup \mathcal{B}_2)\) is called a feasible \(\alpha\)-\(\beta\) transshipment if \[0\leq \mu\leq \psi\quad\text{ and }\quad\mu^1=\sigma_\alpha,\;\; \mu^2=\sigma_\beta.\]
Since \(\psi\) is supported on \(J_1\times J_2\), this is equivalent to requiring \(\mu\) to be a feasible \(\sigma_\alpha\)-\(\sigma_\beta\) flow. The set of all feasible \(\alpha\)-\(\beta\) transshipment is denoted by \[\mathcal{T}=\mathcal{T}(J_1,\mathcal{B}_1,J_2,\mathcal{B}_2,\alpha,\beta,\psi).\]
Remark 2. \(\mathcal{T}\) is the set of couplings of \(\alpha,\beta\) constrained by \(\psi\).
If \(\mathcal{T}\neq \emptyset\), then \(\mathcal{T}\) is a nonempty weakly compact convex set, and one can consider its extreme points. Applying 11, every \(\mu \in \mathcal{T}\) is supported on some \(J_1\times J_2\), and hence automatically reduced and the quotient \(\mathcal{T}/_\sim\) equals \(\mathcal{T}\). Moreover, for any \(\mu\in \mathcal{T}\), the residual graph simplifies to \[R=R([\mu];\psi)=\mu\wedge (\psi-\mu)+\mu^*\wedge(\psi^*-\mu^*)\] because \(\mu,\psi\) are supported on \(J_1\times J_2\), while \(\mu^*,\psi^*\) are supported on \(J_2\times J_1\).
As a corollary of 11, we obtain the following characterization of extreme feasible flows.
Corollary 3. A measure \(\mu\) is an extreme point of \(\mathcal{T}\) if and only if there is no reduced circulation \(\gamma\) such that \[0< \gamma\leq \mu\wedge (\psi-\mu)+\mu^*\wedge(\psi^*-\mu^*) .\]
It remains to check whether \(\mathcal{T}\neq \emptyset\). [7] gives a Hall-type characterization for the existence of feasible transshipments without the constraint measure \(\psi\). Here we give a Hall-type characterization of the constrained version under certain assumptions on \(\psi\).
Proposition 2. A measurable bipartite graph between \(J_1\) and \(J_2\) is a Borel set \(E\subseteq J_1\times J_2\) such that for every \(S\in\mathcal{B}_1\), \[N(S):=\{y\in J_2:\exists x\in S,\;(x,y)\in E\}\] belongs to \(\mathcal{B}_2\). Assume that \(\psi\) is supported on \(E\), and that for every \(S_1\in\mathcal{B}_1\) and every \(S_2\in\mathcal{B}_2\) with \(S_2\subseteq N(S_1)\), one has \[\psi(S_1\times S_2)\ge \beta(S_2).\] Then \(\mathcal{T}\neq \emptyset\) if and only if \[\alpha(S)\leq \beta\big(N(S)\big)\quad \text{ for any S\in \mathcal{B}_1}.\]
Proof. Necessity: Let \(\mu\in\mathcal{T}\). For \(S\in\mathcal{B}_1\), since \(\psi\) is supported on \(E\subseteq J_1\times J_2\) and \(\mu \le \psi\), \[\mu(S\times(J_2\setminus N(S)))=0.\] Therefore \[\alpha(S)=\mu(S\times J_2)=\mu(S\times N(S))\le\mu(J_1\times N(S))=\beta(N(S)).\]
Sufficiency: Assume \(\alpha(S)\le\beta(N(S))\) for every \(S\in\mathcal{B}_1\). We apply 1 to the network system \((J_1\sqcup J_2,\mathcal{B}_1\oplus\mathcal{B}_2,0,\psi)\) with boundary \(\sigma_\alpha- \sigma_\beta\). Equivalently, applying the cut condition to complements, it is enough to prove that for every \(S=S_1\sqcup S_2\) with \(S_i\in\mathcal{B}_i\), \[\psi(S\times S^c)\ge\sigma_\alpha(S)-\sigma_\beta(S)=\alpha(S_1)-\beta(S_2).\] Since \(\psi\) is supported on \(E\subseteq J_1\times J_2\), \[\psi(S\times S^c)=\psi(S_1\times(J_2\setminus S_2)) =\psi(S_1\times(N(S_1)\setminus S_2)).\] By the domination assumption on \(\psi\), \[\psi(S_1\times(N(S_1)\setminus S_2)) \ge\beta(N(S_1)\setminus S_2) \ge\beta(N(S_1))-\beta(S_2) \ge\alpha(S_1)-\beta(S_2).\] Thus the cut condition holds and \(\mathcal{T}\ne\emptyset\). ◻
Remark 3. Without the condition that for every \(S_1\in\mathcal{B}_1\) and every \(S_2\in\mathcal{B}_2\) with \(S_2\subseteq N(S_1)\), we have \[\psi(S_1\times S_2) \geq \beta(S_2),\] the theorem fails, as shown in [19].
A classic application of discrete submodular flows is Frank’s generalization of Nash-Williams’ strong orientation theorem [16]. It states that finding an edge orientation of an undirected graph where the in-degree of every subset is bounded below by a supermodular function is equivalent to finding a feasible submodular flow. Using our framework, we can generalize this result to standard Borel spaces as follows.
In this section we fix a standard Borel space \((J, \mathcal{B})\) and a trivial flow \(\Lambda \in \mathcal{M}_+(\mathcal{B}^2)\) such that \(\Lambda(\Delta_J) = 0\). Equivalently, \(\Lambda=\Lambda^*\). A fractional orientation of \(\Lambda\) is a measure \(\mu \in \mathcal{M}_+(\mathcal{B}^2)\) such that \[\mu + \mu^* = \Lambda.\] Note that this implies \(0 \leq \mu \leq \Lambda\). For any subset \(X \in \mathcal{B}\), the inflow into \(X\) under the orientation \(\mu\) is \(\mu(X^c \times X)\).
Suppose we are given a continuous supermodular set function \(h \colon \mathcal{B}\to \mathbb{R}_{\geq 0}\) with \(h(\emptyset) = h(J) = 0\), representing a minimum inflow demand required to maintain network connectivity. We seek an orientation \(\mu\) satisfying the continuous degree constraint: \[\label{eq:orientation95demand} \mu(X^c \times X) \geq h(X) \textrm{ for all } X \in \mathcal{B}.\tag{1}\]
By transforming this into a measurable submodular flow problem, we obtain the following continuous analogue of Frank’s Orientation Theorem.
Proposition 3. Let \(h\) be a continuous supermodular function on \(\mathcal{B}\) with \(h(\emptyset) = h(J) = 0\). There exists a fractional orientation \(\mu\) of \(\Lambda\) satisfying \(\mu(X^c \times X) \geq h(X)\) for all \(X \in \mathcal{B}\) if and only if \[\label{eq:orientation95condition} h(X) \leq \Lambda(X \times X^c) \quad \text{for all } X \in \mathcal{B}.\qquad{(2)}\]
Proof. Necessity is immediate, since \[\mu(X^c\times X)\leq\Lambda(X^c\times X)= \Lambda(X\times X^c)\] for every \(X\in\mathcal{B}\), where the last equality uses \(\Lambda=\Lambda^*\).
For sufficiency, we fix a Borel linear order \(\prec\) on \(J\), which exists on every standard Borel space, and define \[\Omega:=\{(x,y)\in J\times J\;:\; x\prec y \},\qquad \mu_0:=\Lambda|_{\Omega}.\] Since \(\Lambda\) is a trivial flow and \(\Lambda(\Delta_J) = 0\), we clearly have \(\mu_0 + \mu_0^* = \Lambda\).
Any orientation \(\mu\) can be generated by reversing a portion of the flow in \(\mu_0\). Specifically, let \(\theta \in \mathcal{M}_+(\mathcal{B}^2)\) be a flow such that \(0 \leq \theta \leq \mu_0\). We define the new orientation as \[\mu := \mu_0 - \theta + \theta^*.\] It is easy to verify that \(\mu \geq 0\) and \(\mu + \mu^* = \mu_0 + \mu_0^* = \Lambda\). For this \(\mu\), the inflow into \(X\) is calculated as: \[\begin{align} \mu(X^c \times X) &= \mu_0(X^c \times X) - \theta(X^c \times X) + \theta^*(X^c \times X) \\ &= \mu_0(X^c \times X) - \theta(X^c \times X) + \theta(X \times X^c) \\ &= \mu_0(X^c \times X) + \partial\theta(X). \end{align}\] Thus, the inflow constraint 1 becomes \(\partial\theta(X) \geq h(X) - \mu_0(X^c \times X)\).
Since \(\partial\theta(X^c) = - \partial\theta(X)\), substituting \(X\) with \(X^c\) gives: \[\partial\theta(X) \leq \mu_0(X \times X^c) - h(X^c).\] Define the set function \[\varphi(X) := \mu_0(X \times X^c) - h(X^c).\] Note that \(\mu_0(X \times X^c)=\kappa_{0,\mu_0}(X)\), which is submodular, and \(h\) is supermodular which implies \(-h(X^c)\) is also submodular. Thus, \(\varphi\) is a continuous submodular set function with \(\varphi(\emptyset) = \varphi(J) = 0\).
The problem is now reduced to finding a feasible submodular flow \(\theta\) in the network system \((J, \mathcal{B}, 0, \mu_0, \varphi)\). By 5, such \(\theta\) exists if and only if for all \(X \in \mathcal{B}\), \[- \mu_0(X^c \times X) \leq \varphi(X) = \mu_0(X \times X^c) - h(X^c).\] Rearranging this inequality yields \[h(X^c) \leq \mu_0(X \times X^c) + \mu_0(X^c \times X) = (\mu_0 + \mu_0^*)(X \times X^c) = \Lambda(X \times X^c).\] Since \(X\) ranges over \(\mathcal{B}\) and \(\Lambda\) is symmetric, this is exactly condition ?? , which completes the proof. ◻
It remains to understand when the fractional orientation can be chosen to be an orientation. Since \(\mu+ \mu^*=\Lambda\), an orientation corresponds to choosing one direction \(\Lambda\)-almost everywhere; equivalently, \[\frac{\mathrm d\mu}{\mathrm d\Lambda}\in\{0,1\} \qquad \Lambda\text{-a.e.}\] This is also equivalent to \(\mu\wedge\mu^*=0\). In the finite setting, integrality follows from the totally dual integral property of the submodular flow problem. In the measurable setting the corresponding non-fractional problem is more delicate. We leave it as a problem.
Question 1. Under what circumstances can the fractional orientation \(\mu\) given by 3 be chosen such that \(\mu \wedge \mu^* = 0\)?
The second author would like to express his sincere gratitude to Kristóf Bérczi for the warm hospitality during his visit to the Alfréd Rényi Institute of Mathematics. He is also grateful to László Lovász for sharing with him the problem of extending extreme points of basic minorizing charges of coverage functions, which motivates part of this work.