Consider a graph tree $T$, where we are given $k > 1$ unique pairs of nodes $\{u_1,v_1\}\dots \{u_k,v_k\}$. Let $P_{i}$ denote the unique path on $T$ between $u_i$ and $v_i$. Then, my problem is to efficiently find the intersection of all paths $\bigcap_{i=1}^k P_i$ (in terms of vertices). Note that the intersection is also a path.

A first algorithm which I could come up with works as follows; First, set a counter for each edge and vertex of $T$ to 0. Root $T$ arbitrarily to make it a rooted tree. For each $i=1\dots k$, we can find $P_{i}$ in $|P_{i}|$ time by processing the nodes with largest depth first (and simultaneously if they have the same depth). Then, simply increase the counter by one for all vertices and edges in $P_{i}$. After doing this for all edges, we can check which edges and vertices have count $k$ to determine the intersection.

This algorithm runs in $O(|T| + \sum_{i=1}^k |P_{u_i,v_i}|$). Moreover, it still feels quite inefficient; an edge may be checked multiple times even though we already have determined that the edge is not in the intersection. I believe that there may be some algorithm which runs in (close to) $O(|T| + k)$ instead. Do you have any suggestions? Partial answers or ideas are also welcome.

  • $\begingroup$ Consider set operations. $\endgroup$
    – greybeard
    Oct 17 at 10:31
  • $\begingroup$ @greybeard Maybe I am misunderstanding you, but note that the paths $P_i$ are not explicitly given as input. Even simply finding them/enumerating them already would match the time complexity of the algorithm which I describe above. $\endgroup$ Oct 17 at 10:40

1 Answer 1


Here is a useful fact: in a tree, the intersection of two paths, $P_1 \cap P_2$, is another path (or is empty).

Also, you can compute that path explicitly in $O(1)$ time using a few least common ancestor queries and a case analysis. The resulting intersection will also be represented by a pair of vertices (the endpoints of that path).

Therefore, you can compute the intersection $P_1 \cap \dots \cap P_k$ of $k$ paths in $O(k)$ time.

(You will have to do a $O(|T|)$-time preprocessing step on the tree to build up the data structure needed to support $O(1)$-time LCA queries. I assume this is OK.)

See also Checking whether two paths are intersecting in a tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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