4

How can I find a least common ancestors of multiple nodes in a directed acyclic graph?

I've found quite a few papers on the topic but they all seem to find LCAs in DAG for two nodes.

Are there good algorithms for multiple nodes?

Charles
  • 50,943
  • 13
  • 104
  • 142
yper
  • 41
  • 1
  • 3
  • 1
    Is there any reason why you can't just use the algorithm for two nodes recursively? – Dennis Meng Jul 16 '12 at 22:11
  • 3
    To clarify what @DennisMeng means: `lca(A, B, C) == lca(A, lca(B, C))`. Also note that `lca(A, B, C, D) == lca(lca(A, B), lca(C, D))`, so take your list of `n` nodes, build a binary tree on top of it that is as balanced as possible, and you only have to apply the binary `lca` `Θ(log n)` times. –  Jan 03 '13 at 23:44
  • dup? [LCA in DAG](http://stackoverflow.com/questions/14865081/algorithm-to-find-lowest-common-ancestor-in-directed-acyclic-graph) – vzn Mar 07 '14 at 23:03
  • @vzn At a glance, it looks like the question you linked asks about LCA for two nodes, but OP here is explicitly looking for the case where there's 3 or more. – Dennis Meng Jun 28 '14 at 08:06
  • as the answer below & rhymoids comments indicate, apparently finding LCAs of multiple nodes is usually done recursively & iterating over pairwise LCAs. – vzn Jun 28 '14 at 15:31

2 Answers2

2

Maybe you can modify the algorithm which is used for trees in a way that adopts to DAGs as well.

As you may know,there is an algorithm for finding LCA in trees with pre-process of O(nlgn) and process of O(1) for each query,so finding LCA of k nodes needs O(k) . More details about this algorithm can be found here.
ye9ane
  • 1,959
  • 3
  • 18
  • 31
1

As @DennisMeng, @vzn and @user824425 already pointed out in the comments, under certain circumstances (!) the LCA of more than two nodes can be computed by pairwise recursive application of the (binary) LCA operator, e.g.:

lca(A, B, C, D) = lca(A, lca(B, lca(C, D)))

In functional programming, this is basically equivalent to a reduce (or fold) operation.

However, this is only true for DAGs that are Multitrees (or, alternatively, diamond-free posets). For general DAGs that don't have the multitree/diamond-free poset property, this approach will unfortunately not work.

Consider the following DAG representing a class hierarchy that features multiple inheritance (all edges are directed from the bottom to the top; the X indicates a crossing of two directed edges):

        Any
       /   \
  Boolean Value 
      |  X  |  \
    False True Unknown

Notably, the True and False nodes both have two direct ancestors, Boolean and Value. The first problem here is that this requires an LCA operator that can return more than one node, such as JGraphT's getLCASet. Now, let's say we wanted to compute the LCA of {False, True, Unknown}: by simply looking at the graph, it is pretty obvious that Value is a direct ancestor of all three nodes. Direct pairwise reduction is no longer applicable, because the binary getLCASet operator can return more than one node, but conceivably one could use a stack-like approach where the computed ancestors get pushed back to the list of nodes. However, this does not produce the correct result, e.g.:

  True, False, Unknown
     \   /
     (LCA)
     /   \
Boolean, Value, Unknown
     \   /
     (LCA)
       |
      Any, Unknown
        \   /
        (LCA)
          |
         Any
raner
  • 1,175
  • 1
  • 11
  • 21