# Edmonds-Giles theorem

Let D=(V,A) be a digraph, and let b be a crossing submodular function on V. Let $f,g \in {\mathbb R}^A$ such that $f \leq g$.

Theorem (Edmonds and Giles [1]). The system $\max\{cx: f \leq x \leq g,\ \varrho_x(Z)-\delta_x(Z) \leq b(Z) \text{ for every }Z \subseteq V\}$ is totally dual integral.

A vector $x \in {\mathbb R}^A$ that satisfies the above inequalities is called a submodular flow. There are several different types of polynomial algorithms for deciding the existence of a submodular flow [2][3] and for finding a minimum cost submodular flow [4][5][6][7].

## References

1. J. Edmonds, R. Giles, A min-max relation for submodular functions on graphs, in: Studies in Integer Programming (Proceedings of the Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), 1977, 185–204. DOI link, Google Books link.
2. A. Frank, Finding feasible vectors of Edmonds-Giles polyhedra, DOI link, author link
3. A. Frank, Z. Miklós, Push-relabel algorithms for matroids and submodular flows, DOI link, author link
4. W.H. Cunningham, A. Frank, A primal-dual algorithm for submodular flows, DOI link, author link
5. L. Fleischer, S. Iwata, S.T. McCormick, A faster capacity scaling algorithm for minimum cost submodular flow, DOI link, author link
6. S. Iwata, S.T. McCormick, M. Shigeno, A fast cost scaling algorithm for submodular flow, DOI link, author link
7. S. Iwata, S.T. McCormick, M. Shigeno, A strongly polynomial cut canceling algorithm for minimum cost submodular flow, DOI link, author link