The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint paths or not ? The solution I thought was that the LCA of (u1 and v1) should be the ancestor of u2 or v2 or vice versa . But this is a wrong solution since it does not always work out correctly .
3
-
$\begingroup$ Ancestor, LCA ... You did not say your tree is rooted. Assuming it is, how was the root chosen? Is there anything specific about it? I could also wonder how the tree is specified as I know various ways of specifying a rooted tree. Heavy user name you got! $\endgroup$– babouCommented Jun 10, 2014 at 12:13
-
$\begingroup$ Are you saying that you're given the paths? Because then all you have to do is see if the two arrays/sets/lists have a common element, say by putting the elements in a hashset. $\endgroup$– gardenheadCommented Jun 10, 2014 at 20:36
-
1$\begingroup$ @StephenBly There is exactly one path between any pair of nodes in a tree. So a path is defined by its two endpoints (you don't have the actual paths). But good point and OP should stress this point in question. $\endgroup$– mrkCommented Jun 11, 2014 at 0:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
This is a standard exercise. Try drawing some pictures with the different cases, and you'll see how to formulate a criterion for when they overlap, in terms of the lowest common ancestor.
Just computing $LCA(u_1,v_1)$ isn't gonna be enough, because that only gives you information about the first path, and doesn't depend at all on the second path. So try computing the LCA of some other pair of nodes.
Since this looks like an exercise, I'm not going to solve your problem for you, but I'll describe for you how you can approach this problem so you can solve it yourself.
Every path falls into one of two categories: either it goes down (i.e., $v_1$ is a descendant of $u_1$); or it goes up and then down (i.e., $u_1$ and $v_1$ are descendants of some common ancestor, $w_1 = LCA(u_1,v_1)$, where $w_1 \ne u_1$ and $w_1 \ne v_1$). So, there are two possibilities for the first path, and two possibilities for the second path: four cases in all.
You can quickly classify each path, put it into these categories, and find the endpoints and the common ancestor. (Exercise for you: How?)
Now, you have four cases. For each case, draw some pictures and work out the criteria under which the two paths intersect. It's straightforward.
For instance, let's take the first of the four cases. Suppose both paths go only down: $u_1$ is an ancestor of $v_1$, and $u_2$ is an ancestor of $v_2$. Can you figure out how to tell whether they overlap? Some tips: If $LCA(u_1,u_2)=u_1$, what can you conclude? If $LCA(u_1,u_2)=u_2$, what can you conclude? If $LCA(u_1,u_2)$ is something else, then what can you conclude?
Now do similar reasoning for each of the four cases.
Note: I am also assuming that you have a rooted tree; otherwise, the problem is not well-defined (as the LCA is not defined in non-rooted trees).
My thanks to @babou for his helpful comments and feedback on an earlier version of this answer.
