7
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ In “remove all its edges”, does the “it” refer to the tree, or just to the root? $\endgroup$ – Emil Jeřábek supports Monica May 17 '18 at 9:40
  • $\begingroup$ It refers just to the root. $\endgroup$ – Dmitri Urbanowicz May 17 '18 at 10:32
7
$\begingroup$

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

$\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.