<p>What is the current best bound for the following problem in DAG: "For any pair of vertices in a given graph G, return all the LCAs of the same"?</p>

<p><strong>Edit:</strong> I am working on all-pair reachability problem in DAG and I strongly feel that I can achieve O(mn) time for the problem stated above by extending my approach. I have searched the internet enough to find the current best algorithm for this problem but all I can find is the solution to this problem: "For any pair of vertices in a given graph G, return one LCA for the same". And this problem is trivial and easy. And you don't need to google it for me! And read the problem correctly, it has more content than simply "lca" and "dag"! So, can someone please tell me now about the current best algorithm for the problem stated.</p>

CC BY-SA 3.0
2013-06-27T13:16:34.047Z
To summarise: Bender et al. http://www.cs.stonybrook.edu/~bender/pub/JALG05-daglca.pdf show how to find one LCA, in time $\tilde{O}(n^{2.688})$.  In contrast, you want to generate the set of all LCAs, and are wondering whether an algorithm is known to do this in $o(mn)$ time.  Is this correct?
András Salamon
CC BY-SA 3.0
2013-06-27T16:10:42.673Z
@AndrásSalamon Indeed!
rkjha
CC BY-SA 3.0
2013-06-27T17:22:10.973Z
@rkjha maybe you can clarify this in the question and remove the discussion in the edit ?
Suresh Venkat
<randomized-algorithms><directed-acyclic-graph>
Lowest Common Ancestor Problem in Directed Acyclic Graphs
rkjha
# Lowest Common Ancestor Problem in Directed Acyclic Graphs

(Asked by: username_0 on 2013-06-22)

What is the current best bound for the following problem in DAG: "For any pair of vertices in a given graph G, return all the LCAs of the same"?

**Edit:** I am working on all-pair reachability problem in DAG and I strongly feel that I can achieve O(mn) time for the problem stated above by extending my approach. I have searched the internet enough to find the current best algorithm for this problem but all I can find is the solution to this problem: "For any pair of vertices in a given graph G, return one LCA for the same". And this problem is trivial and easy. And you don't need to google it for me! And read the problem correctly, it has more content than simply "lca" and "dag"! So, can someone please tell me now about the current best algorithm for the problem stated.

**Tags:** randomized-algorithms, directed-acyclic-graph
> **Comments:**
> **username_1**: To summarise: Bender et al. http://www.cs.stonybrook.edu/~bender/pub/JALG05-daglca.pdf show how to find one LCA, in time $\tilde{O}(n^{2.688})$.  In contrast, you want to generate the set of all LCAs, and are wondering whether an algorithm is known to do this in $o(mn)$ time.  Is this correct?  
> **username_0**: @AndrásSalamon Indeed!  
> **username_2**: @rkjha maybe you can clarify this in the question and remove the discussion in the edit ?  

---

## 0 answers

