Edmonds' matching polytope theorem
From Egres Open
Theorem (Edmonds)[1]. Let G=(V,E) be an undirected graph. The convex hull of the characteristic vectors of matchings of G is described by the linear system
[math]x \in {\mathbb R}^E_+[/math]
[math]d_x(v) \leq 1[/math] for every [math]v \in V[/math]
[math]x(E[U]) \leq (|U|-1)/2[/math] for every [math]U \subseteq V[/math] with [math]|U|[/math] odd.
It was shown by Cunningham and Marsh [2] that the above system is total dual integral. This result has several generalizations, for example to even factors [3].
References
- ↑ J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, J. of Res. the Nat. Bureau of Standards 69 B (1965), 125-130. NIST link
- ↑ W. H. Cunningham, A. B. Marsh, A primal algorithm for optimum matching, Mathematical Programming Studies 8 (1978), 50-72, Springer link.
- ↑ T. Király, M. Makai, On polyhedra related to even factors, Springer link, EGRES Technical Report.
