on even path problem

There is a natural problem: find a simple even s-t path in an undirected graph.

There is an algorithm in [1]. The following was proposed by M. Babenko as an attempt to get a linear time solution: find 2-connected components (can be done by finding articulation points, see [2] or Chapter 2, exercise 16 in [3]), then each block is either biparate or contains an odd cycle which can be used to produce either odd or even path connecting articulation points.

For the shortest even s-t path problem there is a polynomial algorithm described in [4], page 274: first an auxilary graph is constructed (take two copies of G: G_s, G_t, remove t from G_s, remove s from G_t, connect all other vertices in G_s with their copies in G_t using edges of weight zero, all edges corresponding to edges in G have weight one) then a minimum weighted perfect matching is to be found on auxilary graph. Edges of weight one correspond to a shortest simple even path in G. In [4] the origin of this algorithm is referensed to GLS88 (probably this is [5] but I can't check this since google books hides reference page). Similar algorithm for a shortest odd path is presented in [6] (pp 247-248) and is said to be due to Edmonds (unpublished result), the reader is then asked to reduce an even path problem to matching as an exercise. An O(n^3) algorithm for minimum weight perfect matching problem is described in [3], chapter 11. In abstract to [7] it is pointed out that one can suffice by finding only by finding a single shortest augmenting path (it seems with respect to unweighted matching consisting only of edges connecting different copies of vertexes).

Just as a note a shortest even s-t path (not necessarily simple) can easily be found in linear time: take two copies of V: V',V''. For each edge (u, v) in new graph there are cross edges: (u',v'') and (u'',v'). Then find a shortest s'-t' path.

[1] Andrea S. Lapaugh, Christos H. Papadimitriou. The even-path problem for graphs and digraphs. Networks Volume 14, Issue 4, pages 507–513, Winter 1984. http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/abstract

[2] http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/biconnected_components.html

[3] Bernhard Korte, Jens Vygen. Combinatorial Optimization Theory and Algorithms 4th ed., 2008

[4] Naum Zuselevich Shor, Nondifferentiable Optimization and Polynomial Problems (Nonconvex Optimization and Its Applications), 1998

[5] Grotschel M., Lovasz L., Schrijver A. Geometric Algorithms and Combinatorial Optimization. 1988
[6] L. Lovasz, M. D. Plummer. Matching Theory, 1986
[7] Ulrich Derigs. An efficient Dijkstra-like labeling method for computing shortest odd/even paths // Information Processing Letters Volume 21, Issue 5, 18 November 1985, Pages 253-258