# Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing

I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$? More informally, the restriction is that when the edge is given, we can only proceed in to that direction.

I can simply perform a DFS and return a leaf found. I think this would take $O(d)$ time, where $d$ is the diameter of $T$. However, I'd like to answer a query in $O(1)$ time. Moreover, I'd only like to allow linear preprocessing time. My idea for achieving this was to use a DFS, label leaves, and then label edges when the search backtracks. This idea might work with some additional effort, but I'm really unsure about the details.

"Graph reachability" turned up some results, but maybe they are dealing with more complex problems. I'm happy with any method that uses $O(n+m)$ preprocessing time and answers the queries in $O(1)$ time.

• Is this a homework question, or do you have some application where you need those bounds? My gut says it's impossible, but if you got asked it as homework, presumably a solution exists. – jmite Jul 17 '13 at 16:23
• If nothing else, I think you're preprocessing will likely take $O(mn)$ time, since to get $O(1)$ queries, you'll need a table with an entry for each node-edge pair. (This might come from initializing your table to all True or all False, even if you can quickly fill in the values after). Can you give more detail about your DFS idea? What are you using to label your leaves and edges? – jmite Jul 17 '13 at 18:37
• @jmite There are $2m$ node-edge pairs, since the edge is incident to the node. – Yuval Filmus Jul 17 '13 at 21:40
• @user9214 Your idea sounds like it should work. You should probably remember the "last leaf found" and use it to label nodes when you backtrack, treating forward edges and back edges differently. Try it out and let us know how it went. – Yuval Filmus Jul 17 '13 at 21:41

Yes, I think you can do this in $O(1)$ time. I outline a method below. There's probably a simpler way to do it, but the following should suffice.

Preprocessing. I'll assume we can view your tree as a rooted tree, with some root. In pre-processing, annotate each internal node $w$ with one example of a leaf that is a descendant of $w$. This can be done in $O(n+m)$ pre-processing time, using a very simple top-down traversal (DFS).

Also, define $p^*(\cdot)$ recursively as follows: if $w$ has any siblings, then $p^*(w)=w$; otherwise, $p^*(w)=p^*(v)$ where $v$ is the parent of $w$; and $p^*(r)=r$, where $r$ is the root of $T$. In English, $p^*(w)$ is defined to be the node obtained by starting at $w$ and continuing upwards until we reach a node that has two or more children (or the root). In pre-processing, we'll compute the value of $p^*(w)$ for each node $w$ and store it associated with $w$. This too can be computed in $O(n+m)$ time.

Answering a query. Now, here's how to answer the query return any leaf that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$:

• Case 1: Suppose $u$ is a child of $v$. Then, answering your query amounts to returning any leaf that is a descendant of $u$. This can be done in $O(1)$ time using the annotation on $u$.

• Case 2: Suppose $u$ is the parent of $v$, and $u$ has at least one other child. Then, look at any other child of $u$, call it $w$. Then, answering your query amounts to returning any leaf that is a descendant of $w$. This can be done in $O(1)$ time using the annotation on $w$.

• Case 3: Suppose $u$ is the parent of $v$, and $u$ has no other children. Then let $u'=p^*(u)$ and let $w$ be any other child of $u'$ (not an ancestor of $v$). Then, answering your query amounts to returning any leaf that is a descendant of $w$. This can be done in $O(1)$ time using the annotation on $w$.

In all three cases, the answer to the query can be computed in $O(1)$ time.