An algebraic matching algorithm (Q1586334)

The Tutte matrix of an undirected simple graph \(G=(V, E)\) is the skew-symmetric matrix \(T=(t_{ij})\) with \(t_{ij}=z_e\) or \(-z_e\), when \(\{i,j\}=e\in E\), and \(t_{ij}=0\) when \(\{i,j\}\notin E\), with \(\{z_e\mid e\in E\}\) a set of algebraic independent commuting indeterminates. The rank of the Tutte matrix is precisely twice the size of a maximum matching in \(G\), and hence, \(G\) has a perfect matching, if and only if \(T\) is non-singular. This paper addresses the question to use this result to obtain an efficient algorithm for solving the maximum matching problem on graphs. It is shown that one can find a constant value from \(\{1,\dots, n\}\) \((n=|V|)\) for each indeterminant, such that the rank of this `evaluation' of \(T\) equals the rank of \(T\). Hence, this gives an algorithm to compute (the size of) a maximum matching of \(G\): first find this evaluation, and then compute its rank. This gives a new technique to algorithmically solve the maximum matching problem. The algorithm uses polynomial time, but significantly more than Edmonds' augmenting path algorithm.