# Edmonds-Giles theorem

From Egres Open

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

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

A vector [math]x \in {\mathbb R}^A[/math] 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

- ↑ 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. - ↑ A. Frank,
*Finding feasible vectors of Edmonds-Giles polyhedra*, DOI link, author link - ↑ A. Frank, Z. Miklós,
*Push-relabel algorithms for matroids and submodular flows*, DOI link, author link - ↑ W.H. Cunningham, A. Frank,
*A primal-dual algorithm for submodular flows*, DOI link, author link - ↑ L. Fleischer, S. Iwata, S.T. McCormick,
*A faster capacity scaling algorithm for minimum cost submodular flow*, DOI link, author link - ↑ S. Iwata, S.T. McCormick, M. Shigeno,
*A fast cost scaling algorithm for submodular flow*, DOI link, author link - ↑ S. Iwata, S.T. McCormick, M. Shigeno,
*A strongly polynomial cut canceling algorithm for minimum cost submodular flow*, DOI link, author link