Exact Matching in Matrix Multiplication Time

Abstract

Let $A_0,A_1\in {\mathbf{F}}^{n\times n}$ be square matrices over a finite field $\mathbf{F}$ and consider the matrix pencil $A_0+y{A}_1$ with indeterminate $y$. We observe that, once $A_0+\lambda A_1$ is nonsingular for some $\lambda \in \mathbf{F}$, the polynomial $\det (A_0+y{A}_1)$ can be reconstructed by computing one determinant, one inverse matrix, and the characteristic polynomial of a single matrix. Consequently, this determinant polynomial can be computed in $\mathrm{O}(n^{\omega })$ field operations, avoiding the polylogarithmic overhead of a general polynomial-matrix determinant algorithm in this special setting. Applying this observation to random evaluation of the Tutte matrix of a graph, we obtain a matrix-multiplication-time randomized algorithm for the so-called exact matching problem. Specifically, one can decide, simultaneously for all $k$, whether a given $0/1$-weighted graph has a perfect matching of weight exactly $k$ in $\mathrm{O}(n^{\omega })$ field operations, where $n$ denotes the number of vertices in the graph. We also discuss the analogous extension to the exact linear matroid parity problem and its consequences for a perfect packing of Mader's $\mathcal{S}$-paths of minimum total length and for a shortest cycle through three specified vertices.

20 pages