A note on the separation problem for the matching matroid (Q760436)

For a graph G having vertex set V, the matching matroid of G is the matroid on V that has as its independent sets all subsets X of V such that G has a matching whose set of endpoints contains X. If r is the rank function of this matroid the associated polyhedron \({\mathcal P}\) is defined by \({\mathcal P}=\{x\in {\mathbb{R}}_+^ v: x(A)\leq r(A)\) for all \(A\subseteq V\}\). Thus \({\mathcal P}\) is the convex hull of the incidence vectors of the independent sets of the matching matroid. This paper considers the following separation problem: determine whether a given member x of \({\mathbb{R}}_+^ v\) belongs to \({\mathcal P}\) and, if it does not, find a subset A of V for which \(x(A)>r(A).\) The author solves this problem by reducing it to the problem of finding a minimum-capacity cut on a certain digraph.