snippetMinor
How to make efficient path minimum queries in a tree?
Viewed 0 times
pathefficientmakeminimumhowqueriestree
Problem
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?
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?
Solution
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 $i0$, $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.
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 $i0$, $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.
Context
StackExchange Computer Science Q#134530, answer score: 2
Revisions (0)
No revisions yet.