<p>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&#39;$ be the graph obtained. Then $G$ has $k$ odd-length vertex-disjoint paths between $s$ and $t$ iff $G&#39;$ has $k$ even-length vertex-disjoint paths between $s$ and $t$. </p>

<p>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 [<em>The complexity of finding maximum disjoint paths with length constraints</em>. 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.</p>

<p>Hope this helps.</p>

CC BY-SA 3.0
2012-01-24T06:57:17.243Z
"Hence the Vertex-Disjoint Odd Length Paths problem ***is*** NP-complete."
Kris
CC BY-SA 3.0
2012-03-06T14:30:34.983Z
Thanks for your insight Somnath; the reduction in the paper is very relevant. However, I disagree with your claim that "in the graph constructed, the odd length paths between s and t all have length exactly five"; looking at the example graph in Fig. 5 on page 282 of their paper, (s; w1,1; x1,1; c3; -x1,1; y1,1; z1,1; t) is an odd s-t path of length 7. However, it does seem as if the construction can be used to prove the NP-completeness of my problem; thanks!
Bart Jansen
CC BY-SA 3.0
2012-01-23T16:49:16.167Z
2012-01-23T18:36:22.023Z
2012-01-23T18:36:22.023Z
Somnath
<p>(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.</p>

CC BY-SA 2.5
2010-10-02T14:49:15.787Z
This should be a comment to that answer.
Derrick Stolee
CC BY-SA 2.5
2010-10-03T09:23:34.893Z
@Derrick: You need 15 reputation to add comments, which Karolina didn't then yet have.
Charles Stewart
CC BY-SA 2.5
2010-10-03T12:35:30.610Z
@Charles: Nitpicking: it is 50, not 15.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-03T15:11:36.720Z
Ah, unfortunate. Carry on.
Derrick Stolee
CC BY-SA 2.5
2010-10-02T08:31:49.117Z
2010-10-02T08:31:49.117Z
Karolina Sołtys
<p>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.</p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>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 <a href="http://homepages.cwi.nl/~bgerards/personal/papers/geelen_gerards_reed_seymour_vetta=odd_hadwicher%5B2009%5D.pdf" rel="nofollow">On the odd-minor variant of Hadwiger’s conjecture</a>.</p></li>
<li><p>If the graph is directed then testing for the existence of a single even-length s-t path is already NP-complete.</p></li>
<li><p>The paper <a href="http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/abstract" rel="nofollow">The even-path problem for graphs and digraphs</a> 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.</p></li>
</ol>

<p>Any insights will be much appreciated!</p>

CC BY-SA 2.5
2010-10-02T12:21:58.267Z
The paper does seem very relevant. I can get it on monday, if no one else gets it until then.
domotorp
CC BY-SA 2.5
2010-10-04T10:56:25.680Z
Andras Salamon already sent me a copy; thanks for the offer!
Bart Jansen
<matching><graph-algorithms>
Maximum number of internally vertex-disjoint odd length s-t paths
Bart Jansen
# Maximum number of internally vertex-disjoint odd length s-t paths

(Asked by: username_0 on 2010-10-01)

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](http://homepages.cwi.nl/~bgerards/personal/papers/geelen_gerards_reed_seymour_vetta=odd_hadwicher%5B2009%5D.pdf).
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](http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/abstract) 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!

**Tags:** matching, graph-algorithms
> **Comments:**
> **username_1**: The paper does seem very relevant. I can get it on monday, if no one else gets it until then.  
> **username_0**: Andras Salamon already sent me a copy; thanks for the offer!  

---

## 2 answers

### Answer by username_2 on 2012-01-23. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_3**: "Hence the Vertex-Disjoint Odd Length Paths problem ***is*** NP-complete."  
> **username_0**: Thanks for your insight Somnath; the reduction in the paper is very relevant. However, I disagree with your claim that "in the graph constructed, the odd length paths between s and t all have length exactly five"; looking at the example graph in Fig. 5 on page 282 of their paper, (s; w1,1; x1,1; c3; -x1,1; y1,1; z1,1; t) is an odd s-t path of length 7. However, it does seem as if the construction can be used to prove the NP-completeness of my problem; thanks!  

---

### Answer by username_4 on 2010-10-02. Score: 6

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

> **Comments:**
> **username_5**: This should be a comment to that answer.  
> **username_6**: @Derrick: You need 15 reputation to add comments, which Karolina didn't then yet have.  
> **username_7**: @Charles: Nitpicking: it is 50, not 15.  
> **username_5**: Ah, unfortunate. Carry on.  

---

