0
$\begingroup$

I need to prove/disprove an claim that related to "The longest path problem".

For given directed graph $G(V,E)$ with non negative weight function $w(u,v)$, define $L'(u,v)$ as longest path from $u$ to $v$.

I need prove/disprove that for any given simple path $P(v_1,v_2,\ldots,v_i,\ldots,v_j,\ldots,v_k)$ sub-path $(v_i, v_{i+1}, v_{i+2},\ldots,v_j)$ where $1\le i<j\le k$ is longest simple path from $v_i$ to $v_j$.

In simple words, are the sub-paths of Longest path, are longest path?

What I tried is:

Define path $P(v,\ldots,w,\ldots,z,\ldots,v)$

The longest path is $L'(u,v) = L'(u,w) + L'(w,z) + L'(z,v)$

If $L'(w,z)$ is not the longest path, this means that $L'(u,v)$ is not longest path from $u$ to $v$ $\Longrightarrow$ $L'(w,z)$ is longest path from $w$ to $z$.

Is it corrent prove? I know that for undirected graph this prove is wrong and I have an counterexample.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Couldn't $L'(u,w)+L'(w,z)+L'(z,v)$ fail to be a path? $\endgroup$ – Hagen von Eitzen Jun 7 '14 at 12:02
1
$\begingroup$

For simplicity, lets make all weights equal. Now, if you take two consecutive vertices on this longest path, isn't it possible there is a longer path between those two, which cannot be combined with the original longest path?

Here is an example:

$$1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8$$ Add the following arcs: $6 ->9 ->1 -> 10 -> 7$

Which is the longest path? Which is the longest path from $6$ to $7$?

$\endgroup$
  • $\begingroup$ Even simpler is a triangle. As an undirected graph the longest path between two vertices is length two, despite the sub-path between two adjacent vertices of that path having length one. These undirected counterexamples can be converted to directed ones by replacing each undirected edge with two oppositely directed edges. $\endgroup$ – hardmath Jun 7 '14 at 12:19
  • $\begingroup$ @hardmath The problem is about directed graphs ;) And if you make the triangle directed, is not a counterexample anymore. $\endgroup$ – N. S. Jun 7 '14 at 12:24
  • $\begingroup$ By most definitions a path visits a vertex only once, so by adding directed edges among all possible pairs of three vertices, a longest directed path will have length two. But as with the undirected case, any "sub-path" between two adjacent vertices of a path is not "longest". $\endgroup$ – hardmath Jun 7 '14 at 12:27
  • $\begingroup$ I thought it worth mentioning because the OP is aware of undirected counterexamples. $\endgroup$ – hardmath Jun 7 '14 at 12:30
  • $\begingroup$ L'(1,8) = 1->2->3->4->5->6->7->8 Sub path P(6,7) = 6->7 But the is exists L'(6,7) = 6->9->1->10->7 Thank you N. S. :) $\endgroup$ – Alexander R. Jun 7 '14 at 12:35

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.