##
**Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions.**
*(English)*
Zbl 0542.90068

Progress in combinatorial optimization, Conf. Waterloo/Ont. 1982, 315-361 (1984).

[For the entire collection see Zbl 0535.00030.]

This paper surveys old and new results asserting the total dual integrality of certain systems of linear inequalities, involving directed graphs, crossing families, and sub- and supermodular functions. The basis is a proof technique set up by Edmonds, Giles, Hoffman, Johnson, Lovász and Robertson of first showing that the active constraints in the optimum of the linear program can be chosen to be ”nice” (e.g. ”cross-free” or ”laminar”), and next that nice constraint sets are unimodular. This implies that the linear programs have integer optimum solutions.

The results discussed are König’s matching and covering theorems, Menger’s theorem, Ford-Fulkerson’s max-flow min-cut theorem, Dilworth’s decomposition theorem for partially ordered sets, theorems on shortest paths, common SDR’s and trees, Fulkerson’s optimum branching theorem, the Lucchesi-Younger theorem, Nash-Williams’ orientation theorem, Edmond’s theorems on (poly)matroids and their intersection, extensions of these theorems to submodular flows by Edmonds, Giles, Frank, Tardos, Hoffman’s theory of lattice polyhedra, Grishuhin’s model, König’s edge-colouring theorem, the Hoffman-Schwartz chain model, Edmonds’ branching packing theorem, and results by the author on crossing families, strong connectors and supermodular colourings. A study is made of the interrelations between these results.

This paper surveys old and new results asserting the total dual integrality of certain systems of linear inequalities, involving directed graphs, crossing families, and sub- and supermodular functions. The basis is a proof technique set up by Edmonds, Giles, Hoffman, Johnson, Lovász and Robertson of first showing that the active constraints in the optimum of the linear program can be chosen to be ”nice” (e.g. ”cross-free” or ”laminar”), and next that nice constraint sets are unimodular. This implies that the linear programs have integer optimum solutions.

The results discussed are König’s matching and covering theorems, Menger’s theorem, Ford-Fulkerson’s max-flow min-cut theorem, Dilworth’s decomposition theorem for partially ordered sets, theorems on shortest paths, common SDR’s and trees, Fulkerson’s optimum branching theorem, the Lucchesi-Younger theorem, Nash-Williams’ orientation theorem, Edmond’s theorems on (poly)matroids and their intersection, extensions of these theorems to submodular flows by Edmonds, Giles, Frank, Tardos, Hoffman’s theory of lattice polyhedra, Grishuhin’s model, König’s edge-colouring theorem, the Hoffman-Schwartz chain model, Edmonds’ branching packing theorem, and results by the author on crossing families, strong connectors and supermodular colourings. A study is made of the interrelations between these results.

### MSC:

90C10 | Integer programming |

90B10 | Deterministic network models in operations research |

05C35 | Extremal problems in graph theory |

90C11 | Mixed integer programming |

90C35 | Programming involving graphs or networks |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |

05B35 | Combinatorial aspects of matroids and geometric lattices |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

90C05 | Linear programming |

05C05 | Trees |