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.
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
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?