# Induced subgraph problem in trees

Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for each pair $~(u_i, v_i)~$ there is path connecting this pair of vertices. "Smallest" in the sense that the number of edges being used is the least possible.

Does this problem have some special name? Can anyone offer efficient algorithm to deal with it?

• Define "efficient".
– Raphael
Apr 7 '16 at 14:48
• All vertices of a tree are connected through the root (at least). So if you start from the leafs and remove vertices not in the set of known vertices until you run into a known one you'll achieve what you want. I'm afraid though that the original problem meant a more general graph rather than a tree. Apr 7 '16 at 14:50
• @Raphael I have about $10^5$ vertices and edges and i need to solve a problem in 1 second
– Igor
Apr 7 '16 at 14:56
• @wvxxw My problem is exactly about $~G~$ being tree. I was thinking about leaf-delete approach but it doesn't guarantee that resulting subgraph is minimal
– Igor
Apr 7 '16 at 14:57
• The graph is just the union of the paths connecting the pairs. You can find the subtree you need in $O(n)$ time using a fast LCA data structures. Apr 7 '16 at 15:46

First, notice that, in trees, the path between any pair of vertices is unique. This means that the sub-forest you want is the union of these paths.

To find them, do the following:

• Pick any vertex to be the root of the tree. Orient all the edges towards the root and store the distance from the root at each vertex.

• To process a pair $(u_i,v_i)$ start a walk towards the root from the element of the pair that is farther from it. (Break ties arbitrarily.) As you walk, mark edges. If the walk reaches the other item of the pair, stop. Otherwise do the same thing from the other item of the pair.

• Once all the pairs are processed, output the marked edges.

This is correct, since either $u_i$ and $v_i$ are on a path towards the root or the path between them goes through the root. It's also too slow, since we may end up walking over the same edge multiple times, so we end up with $O(n^2)$ running time.

To speed this up, we can just use a union-find data structure. The edges are partitioned into classes labeled by the lowest vertex they can reach by a path of marked edges. Now when we walk, we can skip upwards every time we encounter a marked edge, at the same time merging any classes that we need to.

With this scheme, marked edges are encountered at most twice, so get a total of $O(\alpha(n)n)$, where $\alpha$ is the inverse Ackermann function.

I am not sure about the name of this problem, but I assume that it is not a famous problem, as it is quite easy to solve.

In each tree, there is only one path between any pair of vertices. Therefore, you just need to run BFS starting from an arbitrary vertex $u_i$ from pairs, until you cover all vertices $u_j$ and $v_j$. You can then remove all subtrees that do not have any vertex $u_i$ or $v_i$ in them. Then, for dvery edge, chech if the cut caused by removal of the edge is separating any pair.

• Your approach does't guarantee minimality of resulting graph since at the end i can have two subtrees connected with an edge which i don't need for any of paths.
– Igor
Apr 7 '16 at 15:04
• You can easily check every edge and see if the resulting cut is separating any pair or not. Does that make sense? Apr 7 '16 at 22:30