# Efficient intersection of multiple paths in a tree

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.

• Consider set operations. Oct 17 at 10:31
• @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. Oct 17 at 10:40

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