<p>The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree).</p>

<p>The same paper states that it is an open problem whether this bound is tight.</p>

<p>[1] D. Breslauer and G. F. Italiano. Near real-time suffix tree construction via the fringe marked ancestor problem. <em>Selected papers from the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011)</em> <a href="https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230</a></p>

CC BY-SA 4.0
2018-05-21T04:45:59.523Z
2018-05-21T04:45:59.523Z
Dmitri Urbanowicz
<p>Consider a forest of rooted trees. The problem is to support two operations:</p>

<ol>
<li>disconnect(v): if v is the root of some tree in the forest, remove all edges of v;</li>
<li>findroot(v): find root of the tree containing node v.</li>
</ol>

<p><strong>Are there known worst-case lower bounds for such operations? In particular, is it possible to support both operations in $O(1)$ worst-case time?</strong></p>

<p>Note that this problem is equivalent to the following version of marked ancestor problem:</p>

<ol>
<li>mark(v): mark node v of the rooted tree, if its direct parent already marked or if v is the root;</li>
<li>firstmarked(v): return nearest marked ancestor of v.</li>
</ol>

<p>There is a known lower bound trade-off if we allow mark(v) to mark any node:</p>

<blockquote>
  <p>We present a new lower bound for the marked ancestor problem in the cell probe model with word size b between the update time $t_u$ and the query time $t_q$, $$t_q = \Omega(\frac{\log n}{\log(t_u b \log n)})$$</p>
  
  <h3><a href="https://pdfs.semanticscholar.org/b392/52b42e63ef604fb1bee905e2e4262b12bfbb.pdf" rel="noreferrer">BRICS RS-98-7 Alstrup et al.: Marked Ancestor Problems</a></h3>
</blockquote>

<p>For a reasonable word size $b$, this trade-off implies that it is impossible to support both operations within $O(1)$ worst-case time.</p>

<p>Alstrup et al. prove the same trade-off for various related problems. However I couldn't find any assertions about my version: their proof technique seems to rely on arbitrary gaps between marked nodes.</p>

CC BY-SA 4.0
2018-05-17T09:40:09.563Z
In “remove all its edges”, does the “it” refer to the tree, or just to the root?
Emil Jeřábek
CC BY-SA 4.0
2018-05-17T10:32:25.357Z
It refers just to the root.
Dmitri Urbanowicz
<ds.data-structures><lower-bounds><tree>
How fast can we find and disconnect roots in a forest?
Dmitri Urbanowicz
# How fast can we find and disconnect roots in a forest?

(Asked by: username_0 on 2018-05-13)

Consider a forest of rooted trees. The problem is to support two operations:

1. disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
2. findroot(v): find root of the tree containing node v.

**Are there known worst-case lower bounds for such operations? In particular, is it possible to support both operations in $O(1)$ worst-case time?**

Note that this problem is equivalent to the following version of marked ancestor problem:

1. mark(v): mark node v of the rooted tree, if its direct parent already marked or if v is the root;
2. firstmarked(v): return nearest marked ancestor of v.

There is a known lower bound trade-off if we allow mark(v) to mark any node:

> We present a new lower bound for the marked ancestor problem in the cell probe model with word size b between the update time $t\_u$ and the query time $t\_q$, $$t\_q = \Omega(\frac{\log n}{\log(t\_u b \log n)})$$
>
> ### [BRICS RS-98-7 Alstrup et al.: Marked Ancestor Problems](https://pdfs.semanticscholar.org/b392/52b42e63ef604fb1bee905e2e4262b12bfbb.pdf)

For a reasonable word size $b$, this trade-off implies that it is impossible to support both operations within $O(1)$ worst-case time.

Alstrup et al. prove the same trade-off for various related problems. However I couldn't find any assertions about my version: their proof technique seems to rely on arbitrary gaps between marked nodes.

**Tags:** ds.data-structures, lower-bounds, tree

> **Comments:**
> **username_1**: In “remove all its edges”, does the “it” refer to the tree, or just to the root?  
> **username_0**: It refers just to the root.  

---

## 1 answers

### Answer by username_0 on 2018-05-21. Score: 7 | Accepted answer

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree).

The same paper states that it is an open problem whether this bound is tight.

[1] D. Breslauer and G. F. Italiano. Near real-time suffix tree construction via the fringe marked ancestor problem. *Selected papers from the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011)* <https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230>


---

