An augmenting path algorithm for linear matroid parity (Q1087880): Difference between revisions

Given a graph G and a matching M on VG, a matroid matching in (G,M) is a matching in G whose incident vertices are independent in M. The first successful approach to this problem is due to \textit{L. Lovász} [Algebraic methods in graph theory, Vol. II, Conf. Szeged. 1978, Colloq. Math. János Bolyai 25, 495-517 (1981; Zbl 0478.05027)]. The authors present a new algorithm for the problem of finding a maximum matching, assuming M represented over a field. The classical notion of augmenting paths is extended via the definition of augmenting sequences. Those sequences alternate edges relative to a matching, where successive edges are not required to have a common end. Rather, some sets of vertices obtained from the matching and the sequence must have the same span. This is adequate, as it is proved that a matching is maximum iff it does not allow an augmenting sequence. Augmenting sequences are hard to find generally; the key to the algorithm is an creating mock augmenting sequences in which the span conditions are verified with some of the elements of M substituted by calculated vectors in the vector space spanned by the vectors representing M. The algorithm yields a proof of Lovász's min-max relation, and runs in time O(m.t(n)), where \(m=VG\), \(n=r(M)\) and t(n) is the time spent for multiplying \(n\times n\) matrices. The paper is written in the framework of the special case where G is a collection of independent edges; there is an easy polynomial reduction of the general case to this special case.