1
$\begingroup$

Let’s say we are talking about a simple undirected graph with no loops and no multiple edges. But not necessarily bipartite. And we need to find its matching number. Do we have to find a maximum matching first or can we just apply some “quick” spectral theory magic to get the matching number directly? And by “quickly” I mean better than $O(e\sqrt{n})$, at which point we can just use Micali-Vazirani general graph maximum matching algorithm.

$\endgroup$
2
  • $\begingroup$ MV80 didn't instantly decode to a matching algorithm for me, so you might like to make that more explicit. $\endgroup$
    – Ben Barber
    Oct 31, 2021 at 15:47
  • $\begingroup$ @BenBarber, good point, replaced with a proper algorithm name and a link $\endgroup$
    – Iterokun
    Oct 31, 2021 at 20:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.