# Dynamic Tree Marked Ancestor Queries

Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it must be possible to insert leaves as well as internal nodes. Deletion is not needed. $M$ can only grow by adding new vertices as they are inserted into $V$ (no existing vertices of $V$ will be added to $M$ at a later point in time).

I need an algorithm that given any vertex $v \in V$ (not necessarily in $M$), it will find the nearest ancestor $u \in M$ of $v$, with space preferably being not worse than linear in $|V|$ and/or $|M|$ and time being somewhat logarithmic in $|M|$. Also the updates should be efficient.

This is known as the Marked Ancestor Problem [1] and also goes under the names of two-dimensional range searching and union-find problems. The problem with [1] is that for once it doesn't support insertion of internal nodes, and also it is extremely abstract and I definitely can't derive an algorithm and an implementation from it.

Also in my case, a solution involving Informative Labeling [2] would be highly desirable.

• [1] S. Alstrup, T. Husfeldt and T. Rauhe, Marked Ancestor Problems. focs, pp.534, 39th Annual Symposium on Foundations of Computer Science, 1998
• [2] D. Peleg, Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pp. 579--588, 2000

Here is another approach, maybe it can be "fixed": I can maintain versions of the tree which are linearized by a total order, one using pre-order traversal, the other using post-order traversal, using an approach developed by Dietz [3]. With these two lists I can query in $O(1)$ whether a vertex $u$ is an ancestor of another vertex $v$ in the tree ($u$ must be left of $v$ in the pre-order list and right of $v$ in the post-order list). If I could organize my vertices $M$ in a way that I can find the nearest ancestor of $v$ in logarithmic or polylogarithmic time, the problem is solved. Right now I can just go through all elements of $M$ and collect the nearest ancestor (closest to $v$ in the lists) in $O(|M|)$...

• [3] P. Dietz, Maintaining order in a linked list. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122--127, 1982
• What does it mean to "insert an internal node"? – Jeffε Apr 21 '11 at 4:45
• @JeffE -- many approaches make the compromise to allow tree modification only at the leaves. That is, the tree can grow only by adding leaves, or shrink by deleting leaves. Ideally I would be able to insert a vertex between two existing vertices. Of course, this can be simulated by removing the subtree first and and then re-adding all its vertices, but this comes with a huge performance penalty. However -- if I can manage to implement the dynamic version of Alstrup at all, it would already make my project advance quite a bit. So the middle paragraph is the most important one. – 0__ Apr 21 '11 at 10:53
• You may be asked to add any vertices to M later, and to handle this you have to remember the tree itself. Therefore any data structure for your task requires Ω(|V|) space (more precisely Ω(|V| log |V|) bits). (This may not apply to schemes based on informative labeling, which I do not know well.) – Tsuyoshi Ito Apr 21 '11 at 11:25
• @Tsuyoshi -- That is correct. I should be more precise here: In fact I have multiple subsets of V, because there are different assignments possible, so there is a subset M, a subset N, etc. So I do keep track of the whole V, but I separately maintain M, N, etc.; each of the sets should require as little space as possible; at worst, it shouldn't grow exponentially, but maximally with a linear factor of the size of the tree or subset. – 0__ Apr 21 '11 at 12:08
• I see. That makes more sense. I do not know any answer but hope you get a good answer. – Tsuyoshi Ito Apr 21 '11 at 12:20