the shortest even path to minimum weight perfect matching

Question

Given an edge weighted undirected graph and two vertices s and t, weights are non-negative. Shortest Even Path Problem is to find an s,t-path P having an even number of edges whose total weight is as small as possible. How to reduce Shortest Even Path Problem to minimum weight perfect matching problem

Answer 1

Start with the given graph, imagine painting the nodes blue, and call it G_blue. It has nodes, including s_blue and t_blue, and undirected edges like a_blue <-> b_blue.

Make a copy of the graph, paint its nodes green and call it G_green.

Now reconnect all of the edges, so that a_blue<->b_blue and a_green<->b_green (which have equal weights) become a_blue<->b_green and a_green<->b_blue (which have the same weights).

In this combined graph, every edge is between a blue node and a green node, so every path alternates between blue and green. So every path from s_blue that has a even number of steps, will end on a green node.

Now on this combined graph, seek the minimum-weight path from s_blue to t_green.

Finally, remove the subscripts.