Posted by: atri | November 9, 2011

The curious story of MST algorithms

While talking with Max after class today, I realized I had forgotten to mention a very curious state of affairs for MST algorithms. As I mentioned in a footnote of the current HW, the best known MST algorithm for a graph with $n$ vertices and $m$ edges has a run time of $m\alpha(n,m)$, where $\alpha(n,m)$ is the inverse Akcerman function, which for all practical purposes is no bigger than $5$ (but asymptotically is still not a constant).

Even though the appearance of the inverse Ackerman function is somewhat surprising, the story has another bizarre twist to it. Seth Pettie and Vijaya Ramachandran have a very neat algorithm that computes the MST of any given graph in provably optimal time. However, the curious thing is that no one know what is the exact optimal time. Folks can bound the optimal time from the above and below and but the exact (asymptotic) behavior is still pretty much up in the air!