18
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ The paper does seem very relevant. I can get it on monday, if no one else gets it until then. $\endgroup$ – domotorp Oct 2 '10 at 12:21
  • $\begingroup$ Andras Salamon already sent me a copy; thanks for the offer! $\endgroup$ – Bart Jansen Oct 4 '10 at 10:56
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Hence the Vertex-Disjoint Odd Length Paths problem is NP-complete." $\endgroup$ – Kris Jan 24 '12 at 6:57
  • $\begingroup$ 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! $\endgroup$ – Bart Jansen Mar 6 '12 at 14:30
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This should be a comment to that answer. $\endgroup$ – Derrick Stolee Oct 2 '10 at 14:49
  • $\begingroup$ @Derrick: You need 15 reputation to add comments, which Karolina didn't then yet have. $\endgroup$ – Charles Stewart Oct 3 '10 at 9:23
  • $\begingroup$ @Charles: Nitpicking: it is 50, not 15. $\endgroup$ – Tsuyoshi Ito Oct 3 '10 at 12:35
  • $\begingroup$ Ah, unfortunate. Carry on. $\endgroup$ – Derrick Stolee Oct 3 '10 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.