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].
References:
[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.
[4] arxiv.org/pdf/0807.1620