Problems that feel exponential but are P
For me one of the most efficient algorithms is the Blossom V algorithm that find maximum weight perfect matching in a general graph:

https://en.m.wikipedia.org/wiki/Blossom_algorithm