Maximum number of internally vertex-disjoint odd length s-t paths

Question

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.

1. 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.

2. 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.

3. 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.

4. If the graph is directed then testing for the existence of a single even-length s-t path is already NP-complete.

5. 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!

Answer 1

Firstly note that: given a graph $G=(V,E)$, two distinguished vertices $s,t \in V$ and an integer $k$, the problem of deciding whether there are $k$ internally vertex-disjoint odd-length paths between $s$ and $t$ is polynomially equivalent to deciding whether there exists $k$ even-length paths between $s$ and $t$. The reduction is easy. To reduce from one case to another, simply subdivide each edge adjacent to $t$. Let $G'$ be the graph obtained. Then $G$ has $k$ odd-length vertex-disjoint paths between $s$ and $t$ iff $G'$ has $k$ even-length vertex-disjoint paths between $s$ and $t$.

Therefore, if one of these problems is NP-complete, so is the other. Now Itai, Perl and Shiloach show that the problem of deciding whether there exist $k$ vertex-disjoint paths of length five between $s$ and $t$ is NP-complete [The complexity of finding maximum disjoint paths with length constraints. Networks, Volume 12, Issue 3, pages 277–-286, 1982.] The reduction is from 3SAT and in the graph constructed, the odd length paths between $s$ and $t$ all have length exactly five. Hence the Vertex-Disjoint Odd Length Paths problem in NP-complete and so is the Vertex-Disjoint Even Length Paths.

Hope this helps.

Answer 2

(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.