kactl
kactl copied to clipboard
General Matching has unnecessary factor of 8
In the randomized General Matching code, the code only knows how to extract a perfect matching, so we add up to N additional vertices before computing the matrix inverse which blows runtime up by a factor of 8. This is unnecessary, you can instead just restrict the set of vertices to the basis found in the first run of Gaussian elimination. You also shouldn't need to run Gaussian elimination a second time. (See https://codeforces.com/blog/entry/92400). This would require rewriting matInv's interface a little.