Shortest two-sided cycle

There is a simple polynomial-time algorithm for finding a shortest two-sided cycle of an embedded graph. Note that this problem does not use the embedding except for the signatures. So, this is also an algorithm for finding a shortest even cycle in a signed graph.

Let n = |G|. Subdivide the edges with positive signature 2n+1 times, so each of them is now composed of an even number of new edges. Next, subdivide the edges with negative signature 2n times, so they have now an odd number of pieces. Let G' be the resulting graph after the subdivisions. It is easy to see that a shortest even cycle in G' corresponds to a shortest cycle in G with positive signature.

For finding the shortest even cycle in G', there are algorithms that take polynomial time. An early reference is [1], see also [2]. Another old polynomial-time algorithm for finding a shortest even cycle is based on finding a maximum matching and can be found in [3].

A more complicated solution for this problem (correctness not verified by B.M.) can be found on the arXiv [4].

[1] B. Monien, The complexity of determining a shortest cycle of even length, Computing 31 (1983) 355-369.
[2] R. Yuster, U. Zwick, Finding even cycles even faster. SIAM J. Discrete Math. 10 (1997) 209-222.
[3] M. Grötschel, W.R. Pulleyblank, Weakly bipartite graphs and the max-cut problem.