7
$\begingroup$

Recently in my research I have faced with the following subproblem:

Given a tree $T, |V(T)| = n$ and its vertices are ordered $v_1, \ldots, v_n$ so that $T_i = T_{i-1} - v_i, 1 \le i \le n$ and $T_0 = T$ and every $T_i$ is a tree.

The question is:

Is there any linear-time algorithm which gives $n$ pairs $v_{i_k}, v_{j_k}$, which are ends of a diametral path in $T_k$ for every $1 \le k \le n$ (any one if there are several ones)?

I think this algorithm can be useful for achieving linear-time recognition algorithms from explicit characterizations of various subclasses of trees.

ALSO, another way to think about it:

Is there a data structure for a tree, such that we can insert a new leaf and query for a diametral path in amortized $O(1)$ time? (see comment by Chao Xu).

$\endgroup$
  • $\begingroup$ If I understand right, the vertex ordering you provide is the same as saying it's reverse-topologically sorted with v_n as the root $\endgroup$ – dspyz Feb 2 '14 at 17:08
  • 2
    $\begingroup$ I think it's easier to think of in reverse. Maintaining a data structure for a tree, such that we can insert a new leaf and query for a diametral path in amortized $O(1)$ time. (and for your question, we already know the sequence of inserts) $\endgroup$ – Chao Xu Feb 2 '14 at 17:39
  • $\begingroup$ @ChaoXu, yes, it's really good way to think about it, I will add it to the post. $\endgroup$ – Andrew Ryzhikov Feb 2 '14 at 21:15
  • $\begingroup$ @dspyz, yes, you are right, but all it means only that we delete leafs one-by-one from $T$. $\endgroup$ – Andrew Ryzhikov Feb 2 '14 at 21:21
  • $\begingroup$ What is the complexity of leaf insertion? $\endgroup$ – Obinna Okechukwu Feb 3 '14 at 1:20
1
$\begingroup$

Ok,

I have an algorithm I believe is O(nlog*(n)), that's n log-star(n) (log-star n is constant for all practical purposes), but it's hard to prove and I suppose I could be wrong. The running time guess comes from assuming the path compression step takes amortized O(log*(n)) as it does in a union-find data structure, but I don't remember the proof of that so I don't really know for certain that it applies here. Nonetheless, I certainly can't generate any examples where the path-compression is generally slow and I can prove the other operations are amortized constant time.

Following Chao Xu's suggestion, I'll describe the "insert a new leaf" operation on the data structure.

Each vertex has to contain pointers to 4 other vertices in addition to remembering its depth.

Each vertex $v_i$ must remember:

  1. $v_i$'s deepest descendant

  2. $v_i$'s child on whose branch (1) is contained

  3. $v_i$'s nearest ancestor $w_i$ for whom $w_i(2)$ is not an ancestor of $v_i$

  4. Which child of $w_i$ is an ancestor of $v_i$

In fact for any given vertex (1), (3), and (4) may be outdated, but using path-compression we can bring it up to date in (hopefully) amortized O(log*n) running time using path-compression.

def get_deepest(v): # returns (1)
  if v.deepest == v:
    return v
  v.deepest = get_deepest(v.deepest)
  while True:
    deep_ancest,_ = get_nearest_ignoring_ancestor(v.deepest)
    if (not deep_ancest) or deep_ancest.depth <= v.depth:
      break
    v.deepest = get_deepest(deep_ancest)
  return v.deepest

def get_nearest_ignoring_ancestor(v): # returns tuple containing (3) and (4)
  if v.nia == None:
    return (None, root)
  elif v.nia.child_containing_deepest == v.nia_child_containing_self:
    v.nia,v.nia_child_containing_self = get_nearest_ignoring_ancestor(v.nia)
  return (v.nia, v.nia_child_containing_self)

Now when we add a new vertex $v$, we traverse upwards through each (3) updating the deepest vertex until we find one that doesn't update. If we encounter a vertex $w$ which is on the primary path (this is easy to check because $w$.deepest() will be the same as root.deepest()), then we check if the path between the newly inserted node and the current deepest is longer than the currently known longest path. Then that becomes the new diameter. This check can be done in constant time since we know the depths of the current deepest, the newly inserted node, and also the node $w$ at which the paths pointing to the two diverge. Then the length (number edges in) the new path is just $d(v)+d(deepest)-2 d(w)$

It's easy to see that this algorithm is correct because any diameter must have an endpoint at the deepest node from the root (This is generally true of trees. If you don't believe me you can verify it for yourself) and with every node we insert, we check that either

a) It's the deepest node (in which case, we've just increased the currently longest path by one)

OR

b) There exists an ancestor containing a deeper (or equal) node which is not on the deepest path (so the diameter can't have increased)

OR

c) We check the newly inserted node against the deepest node and compute the length of the new path to see if it's longer than the current longest.

To finish the Python pseudo-code for the algorithm:

#root is the root of the tree, it's parent is None
#cur_opp is the vertex currently farthest from get_deepest(root)

def add_node(v, parent):
  v.deepest = v
  v.child_containing_deepest = None
  v.nia = parent
  v.nia_child_containing_self = v

  root_deepest = get_deepest(root)

  while True:
    v_ancest,_ = get_nearest_ignoring_ancestor(v)
    if not v_ancest:
      check_update_path(root_deepest)
      break
    old_deepest = deepest(v_ancest)
    if v.depth > old_deepest.depth:
      old_deepest.nia = v_ancest
      old_deepest.nia_child_containing_self = v_ancest.child_containing_deepest
      v_ancest.child_containing_deepest = v.nia_child_containing_self
      v_ancest.deepest = v
      update_next = True
    else:
      break
  check_update_path(v)

def check_update_path(v):
  cur_deepest = get_deepest(root)
  if v == cur_deepest:
    return
  common = get_nearest_ignoring_ancestor(v)
  if get_deepest(common) != cur_deepest:
    return
  max_len = len_path(cur_opp, cur_deepest)
  new_len = len_path(v, cur_deepest)
  if new_len > max_len:
    cur_opp = v

def len_path(a,b):
  a_ancest = get_nearest_ignoring_ancestor(a)
  assert get_deepest(a_ancest) == b
  return a.depth + b.depth - 2 * a_ancest.depth

The longest path is just the path from cur_opp to get_deepest(root)

Now to show that the number of deepest-branch changes is amortized constant with each add, just imagine that each time we compare two depths and get d(a) == d(b) (when we stop), we reserve one time unit for later. When a node changes deepest branches, the paths must have first been equal so we use up that time unit.

So now all that remains to prove is that the path-compression step is amortized fast and I unfortunately don't know how to do that.

Please note I haven't tested this code and it is almost certainly buggy. Also, I may have left out some edge cases such as how to insert the first node or what to do in certain situations if a node already is on the primary path. It shouldn't be too hard to account for these.

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