Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time.
It is easy to show that there is a perfect matching for the graph, by using flow and showing a flow of size $|V|/2$.
Using flow networks, we can also use Dinic's algorithm to find the max-flow which is equal to the perfect matching (thus, deriving a perfect matching) in $O(|E|\cdot\sqrt{|V|})=O(|V|^{3/2})$ (Since $E=O(|V|)$).
Can we find a perfect matching in linear time?
Thanks!
There is a classical linear time algorithm of Gabow and Kariv.
The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, you find another vertex which has unused edges, and start a new walk from there. Eventually, you will have decomposed all edges into cycles. If you're careful, you can implement this algorithm in $O(n)$; see Wikipedia for hints.
Since the graph is bipartite, all cycles have even length. Remove from each cycle every other edge to obtain a bipartite 2-regular graph. Now repeat the same process to obtain a perfect matching.
This algorithm works more generally for $d$-regular graphs whenever $d$ is a power of 2. It runs in time $O(m)$ even for non-constant $d$ (here $m$ is the number of edges). Cole, Ost, and Shirra devised an $O(m)$ time algorithm for any value of $d$, Alon devised a simple $\tilde{O}(m)$ algorithm for the same problem, and Goel, Kapralov and Khanna gave a randomized $\tilde{O}(n)$ algorithm in the same setting.
