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(n(2))-time algorithm for finding genealogical distances considerably improving the previously known O(n (2.575)) timebound 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+) (1)/(4-w)), where w = 2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known O(n(w+3)/(2)) time-bound for the general all-pairs LCA problem in dags.