0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Define "efficient". $\endgroup$ – Raphael Apr 7 '16 at 14:48
  • $\begingroup$ 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. $\endgroup$ – wvxvw Apr 7 '16 at 14:50
  • $\begingroup$ @Raphael I have about $10^5$ vertices and edges and i need to solve a problem in 1 second $\endgroup$ – Igor Apr 7 '16 at 14:56
  • $\begingroup$ @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 $\endgroup$ – Igor Apr 7 '16 at 14:57
  • $\begingroup$ 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. $\endgroup$ – Louis Apr 7 '16 at 15:46
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Igor Apr 7 '16 at 15:04
  • $\begingroup$ You can easily check every edge and see if the resulting cut is separating any pair or not. Does that make sense? $\endgroup$ – orezvani Apr 7 '16 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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