When Is the Matching Polytope Box-Totally Dual Integral?

Let G = (V, E) be a graph. The matching polytope of G, denoted by P(G), is the convex hull of the incidence vectors of all matchings in G. As proved by Edmonds [10] [Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69(1-2):125-130.], P(G) is determined by the following linear system pi(G): x(e) (3) 0 for each e is an element of E; x(delta(v)) <= 1 for each v is an element of V; and x(E[U]) <= left perpendicular(1/2)|U|right perpendicular for each U subset of V with |U| odd. In 1978, Cunningham and Marsh [6] [Cunningham W, Marsh A (1978) A primal algorithm for optimum matching. Balinski ML, Hoffman AJ, eds. Polyhedral combinatorics. Mathematical Programming Studies, Vol. 8 (Springer, Berlin), 50-72.] strengthened this theorem by showing that pi(G) is always totally dual integral. In 1984, Edmonds and Giles [11] [Edmonds J, Giles R (1984) Total dual integrality of linear inequality systems. Progress in Combinatorial Optimization (Academic Press, Toronto), 117-129.] initiated the study of graphs G for which pi(G) is box-totally dual integral. In this paper, we present a structural characterization of all such graphs, and develop a general and powerful method for establishing box-total dual integrality.