LCA Queries in Directed Acyclic Graphs

We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the all-pairs LCA problem for the input dag on n vertices and m edges in time O(nm). As a corollary, we obtain an O(n2)-time algorithm for finding genealogical distances considerably improving the previously known O(n2.575) time-bound for this problem. The second method relies on a novel reduction of the all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time $O(n^{{2}+\frac{1}{4-\omega}})$, where ω =2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known $O(n^{\frac{\omega+3}{2}})$ time-bound for the general all-pairs LCA problem in dags.