Efficient intersection of multiple paths in a tree

Question

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.

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.