3
$\begingroup$

I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well.

However, one of the answers also mentions a paper that talks about because of the given scenario above, for DAGs there may be cases where you would want to find the lowest SINGLE common ancestor.

From the limited Abstract linked in the answer above, the paper says this:

We derive a new generalization of lowest common ancestors (LCAs) in dags, called the lowest single common ancestor (LSCA). We show how to preprocess a static dag in linear time such that subsequent LSCA-queries can be answered in constant time. The size is linear in the number of nodes.

We also consider a “fuzzy” variant of LSCA that allows to compute a node that is only an LSCA of a given percentage of the query nodes. The space and construction time of our scheme for fuzzy LSCAs is linear, whereas the query time has a sub-logarithmic slow-down. This “fuzzy” algorithm is also applicable to LCAs in trees, with the same complexities.

Clarification I will look more into this to confirm this is what LSCA is but given the picture below

enter image description here

The LCA of this picture for nodes 8 and 9 is straight forward (it would be 6) but for nodes 3 and 4, the LCA could yield either 1 or 2 because they are at the same level and are both common ancestors. In this case, perhaps it makes more sense to find the LSCA which would be 0 since its the single ancestor of the two.

Specifically I would like to know:

How does finding the LSCA of a DAG affect time complexity compared to finding the LCA which could yield multiple solutions and what are the best methods to achieve it?

$\endgroup$
  • 1
    $\begingroup$ @D.W. While your criticism is understandable, the formulation might be a little hard here regarding that this is the question of a first-time questioneer on this side.. :) Also, the actual question is understandable in that sense that he is "curious how this might affect time complexity". $\endgroup$ – Danny Apr 5 '17 at 21:05
  • $\begingroup$ @D.W. Thanks for your comment. I agree I don't think I was very specific. The truth is I'm not actually fully sure what the definition of a LSCA is so I'm going to try and figure that out. Sorry if this question came off as vague. The paper linked doesn't give access so unfortunately I can't read it which is why I ask the question here. $\endgroup$ – aug Apr 5 '17 at 21:37
  • $\begingroup$ "the paper linked doesn't give access". Have you tried to look for google scholar links for the paper? $\endgroup$ – abc Apr 5 '17 at 21:47
  • $\begingroup$ @newbie I actually just found it! I'm reading it now :) Might try to answer my own question if I can! I am still open to answers if people want to contribute though! $\endgroup$ – aug Apr 5 '17 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.