Treffer: Faster algorithms for finding lowest common ancestors in directed acyclic graphs

We present two new 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). 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 (n2+λ), where A satisfies the equation ω (1, A, 1) = 1 + 2 A and w (1, A, 1) is the exponent of the multiplication of an n x nλ matrix by an nλ x n matrix. By the currently best known bounds on ω(1, λ, 1), the running time of our algorithm is O (n2.575). Our algorithm improves the previously known O (n2.688) time-bound for the general all-pairs LCA problem in dags by Bender et al. Our additional contribution is a faster algorithm for solving the all-pairs lowest common ancestor problem in dags of small depth, where the depth of a dag is defined as the length of the longest path in the dag. For all dags of depth at most It ≤ nα, where α ≈ 0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n x n matrices, that is, O (nω); we also prove that this running time is optimal even for dags of depth 1. For dags with depth h > nα , the running time of our algorithm is at most O (nω. h0.468). This algorithm is faster than our algorithm for arbitrary dags for all values of h> n0.42..