Matching in Regular Bipartite Graphs

It is well known that d-regular bipartite graphs have a perfect matching. Applying this iteratively, it even follows that such graphs can be decomposed into the union of d perfect matchings. (The existence of a matching follows from Hall's theorem, which is probably beaten into students during any combinatorics course.)

But how easy is it to find a perfect matching in a d-regular bipartite graph? The following classic gem finds a matching in O(m) time --- but, oddly enough, it assumes d is a power of two!

Find an Eulerian circuit of the graph in O(m) time, which exists for any even d. Now throw out the 2nd, 4th, 6th, etc edges of the circuit. You are left with a graph that is (d/2)-regular. Recurse to find a matching.

Why do you get a regular graph when you throw out all edges on even positions? Think about it: the edges of the circuit go back and forth between the two parties of the graph. For any vertex v, its d incident edges are grouped into d/2 pairs of consecutive edges. One edge of such a pair appears on an odd position in the circuit, and one on an even position.

This algorithm is due to Gabow and Kariv [STOC'78]. By contrast, obtaining a linear-time algorithm for d not a power of two took until 2001 [Cole-Ost-Schirra]. In SODA'09, [Goel-Kapralov-Khanna] achieved sublinear algorithms for d greater than sqrt(n). The idea is that matchings are so frequent that you can still find one (with care) in a random sample of the graph. 

My interest is not so much with the sublinear complexity, but more with matching in general bipartite graphs (not regular). After you see this beautiful algorithm for matching in regular graphs, it is hard not to feel a bit optimistic that general bipartite matching may also be solvable in O(m) time.