4
$\begingroup$

Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them?

My original idea was to solve Least Common Ancestor Queries on any two nodes (using an Eulerian Tour Tree or the Binary Lifting Method), then to split any path into one or two vertical paths that pass through the LCA. After this, we could process the path minimum query on the vertical paths.

However, processing the path minimum query on a vertical path proved to be pretty hard: in path sum queries (finding the sum of all node values on a path), if we know the sum of all nodes from an ancestor to the parent of node A, and also the sum of all nodes from that ancestor to node B, then the sum of all nodes from node A to node B is just equal to the second value minus the first one. In Range minimum Queries, however, this does not work.

Is there any efficient way to solve this problem? Am I missing something in my current approach?

$\endgroup$
2
$\begingroup$

You can preprocess your tree in time $O(n \log n)$ so to obtain a data that uses $O(n)$ space that can answer path-minimum queries in constant time. See "Bottleneck Edge Queries" in this paper which shows how to answer queries that ask for the edge of minimum weight in the unique path between two given vertices in a tree.

You can easily reduce your problem by splitting each edge into two edges and then setting the weight of each edge incident to a vertex $v$ of the original tree to the weight of $w$ itself.

If you are find with a solution that is easier to implement but requires $O(n \log n)$ space and preprocessing time (rather than the $O(n)$ space of the paper I liked above), and supports $O(\log n)$-time queries, then you can do the following:

Start by constructing a LCA oracle for $T$. To do so consider an Euler tour $E = \langle u_1, u_2, \dots u_{m}\rangle$ of your tree and construct an array $A[1 \dots m]$ where $A[i]$ contains the depth of $u_i$. Here $m=2m-2$. Then construct a range minimum query (RMQ) oracle on $A$, so that the LCA $u_k$ between $u_i$ and $v_j$ with $i<j$ is such that $k$ is the index of the minimum $A[k]$ in $A[i], \dots, A[j]$.

A simple RMQ oracle is the following: for each index $i$ of $A$, and for each $j=0, 1, \dots, \lfloor \log m \rfloor$, store in $B[i, j]$ the index $k$ of the minimum $A[k]$ between $A[i], \dots, A[i+2^j-1]$. All the entries of $B$ can be found in $O(n \log n)$ time since, for $j>0$, $B[i,j]$ is either $B[i, j-1]$ or $B[i + 2^{j-1}, j-1]$.

The answer to a RMQ query $(i,j)$ is then the index of $A$ with the minimum value among the two indices $B[i, \Delta]$ and $B[j- \Delta, \Delta]$, where $\Delta=\lfloor j-i+1 \rfloor$.

We are now able to find the LCA $w$ of two vertices $u$ and $v$ in constant time. Then your problem reduces to the one of finding the vertex of minimum weight in two ancestor-descendant paths, namely those between (i) $w$ and $u$, and (ii) $w$ and $v$.

This can be done using a trick similar to the previous one: For each vertex $z$ at depth $d$ maintain $\delta = \lfloor \log d \rfloor$ values $M[z, 0], \dots, M[z, \delta]$, where $M[z, j]$ is the minimum among the weights of the vertices $z= z_1, z_2, \dots, z_{2^j}$ encountered by walking from $v$ towards the root for $2^j - 1$ steps. Moreover, for each vertex $v$, we explicitly store the $O(\log n)$ vertices $z_{2^j}$.

As before, all the values $M[z,j]$ can be found in $O(n \log n)$ time and a path query on an ancestor-descendant path of length $L \ge 2$ can be answered by letting $\ell = \lfloor \log L \lfloor$ and selecting the minimum among $M[z, \ell]$ and a recursive query for the path of length $L - 2^\ell$ that ends with $z_{2^\ell}$.

The query time can actually be improved to $O(1)$ if you additionally compute a long-path decomposition of your tree. The long path decomposition is defined recursively and is obtained by selecting the longest root-to-leaf path $P$, deleting (the edges and vertices of) $P$ from the tree and returning the union of $P$ with all the long-path decompositions of the trees in the resulting forest.

This decomposition can be found in $O(n)$ time and has the following property: given a vertex $v$, the (unique) path $P_v$ that contains $v$ has a lenght |P_v| not smaller than the height of the subtree rooted in $v$.

Let $P_1, P_2, \dots$ be the paths of the decomposition and for each $P_i$ construct an array $P'_i$ by extending $P_i$ by $|P_i|$ edges towards the root, and writing down the vertex weights along this extended path. Build a RMQ oracle on each of the obtained arrays and, for each $v$, keep a reference to the position of $v$ in the (unique) array associated with the path $P'_v$ such that $v$ is contained in $P_v$. The total size of the arrays is $O(n)$ and hence the total size of the RMQ oracles is $O(n \log n)$.

A query on an ancestor-descendant path can now be answered in $O(1)$ time by first looking at $M[v, j]$ and a then querying the oracle associated with $P'_{z'}$, where $z'=z_{2^\ell}$. This is because $L-2^\ell < 2^\ell$ (by the choice of $\ell$), showing that $P_{z'}$ has length at least $2^\ell-1$, and hence all the remaining $L-2^\ell$ proper ancestors of $z'$ (that were not already considered in $M[v, j]$) must be in $P'_{z'}$.

There is a great paper explaining this technique that combines the lookup table $M$ with this extended path-decomposition. With some additional work you can even get rid of the $O(\log n)$ factor in the space complexity.

$\endgroup$
3
  • $\begingroup$ @D.W. The solution I described here requires $O(n \log n)$ space. More elaborate solutions only require $O(n)$ space are described in the paper I linked. I'll try to clarify this in the answer. $\endgroup$
    – Steven
    Jan 19 at 17:21
  • $\begingroup$ When using your simpler approach, I don't see how the final RMQ lookups can be done in $O(1)$ time: Unlike in the initial RMQ lookup done to find the LCA (which is performed in an array where we have $O(1)$ random access), we can't just jump directly to the $k$-th ancestor of an arbitrary vertex -- unless we have done $O(n^2)$ preprocessing, no? The best approach I can think of is to jump "up" the path towards the root in exponentially smaller steps until hitting the LCA, making the queries $O(\log n)$ (or $O(\log \log n)$ if all outdegrees are > 1). $\endgroup$ Jan 19 at 19:10
  • 1
    $\begingroup$ @j_random_hacker. You are right, my writeup is missing one ingredient. The current solution supports queries in $O(\log n)$ time, but adding a long-path decomposition of the tree it is possible to achieve a $O(1)$ query time. I've edited my answer to increase the claimed query time. I'll add more details on how to obtain the $O(1)$ query time in a couple of hours. Thanks for noticing this! $\endgroup$
    – Steven
    Jan 19 at 21:45
0
$\begingroup$

We consider a tree T where T[v] is the parent of v for any node v. A value x[v] is associated to each node v. I also assume that the depth of each node v is precomputed, and given by depth[v].

Let u and v the two queried nodes. We are looking for the smallest value x[w] for any w on the shortest path between u and v. There may be faster algorithms, but I give one that is linear in the length of this path.

Let us initialize r to min(x[u],x[v]), u' to u, and v' to v. While u' is not equal to v', iterate the following: if depth[u']> depth[v']then set u' to T[u'], otherwise set v' to T[v']; and, in both cases, set r to min(x[u'],x[v']). The result is the final value of ̀r, if I am correct.

$\endgroup$

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.