Maximum number of internally vertex-disjoint odd length s-t paths Let $G$ be an undirected simple graph and let $s,t \in V(G)$ be distinct vertices. Let the length of a simple s-t path be the number of edges on the path. I am interested in computing the maximum size of a set of simple s-t paths such that each path has odd length, and the vertex sets of each pair of paths pairwise intersect only in s and t. In other words, I am looking for the maximum number of internally vertex-disjoint odd-length s-t paths. I think that this should be polynomial-time computable by matching or flow-based techniques, but I have not been able to come up with an algorithm. Here is what I know of the problem.


We may replace the restriction to odd length by even-length; this does not really affect the problem since one transforms into the other if we subdivide all edges incident on s.
If there is no restriction on the parity of the paths then Menger's theorem gives the answer, which can be obtained by computing a maximum flow.
The problem of determining the maximum number of vertex-disjoint odd-length cycles which pairwise intersect only at a given vertex v is computable in polynomial time by a matching trick: build a graph G' as the disjoint union of $(G - {v})$ and $(G - N_G[v])$, adding edges between two copies of the same vertex; a maximum matching in this graph of size $|V(G)| - |N_G[v]| + k$ implies that the maximum number of odd cycles through $v$ is $k$; this construction is described in the proof of Lemma 11 of On the odd-minor variant of Hadwiger’s conjecture.
If the graph is directed then testing for the existence of a single even-length s-t path is already NP-complete.
The paper The even-path problem for graphs and digraphs by Lapaugh and Papadimitriou might be relevant, but unfortunately our library does not subscribe to the online archive and we do not have a paper copy.


Any insights will be much appreciated!
(It's not an answer, but I can't comment yet) I think the above answer doesn't work, because it doesn't guarantee that the paths would be vertex disjoint. One path could use u', and the other u" in G'; in G they would use the same vertex u.