Faster Algorithms for All-Pairs LCA in DAGs

Let G = (V, E) be an n-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices u and v is a common ancestor w of u and v such that no descendant of w has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pair of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines, and have running time ranging from O(n^{2.687}) [Bender et al. SODA’01] down to O(n^{2.615}) [Kowaluk and Lingas ICALP’05] and O(n^{2.569}) [Czumaj et al. TCS’07]. In this paper we make the first improvement of the running time in 13 years, namely we present a O(n^{2.447}) algorithm for this problem. Our key tool is a fast algorithm to partition the vertex set of the transitive closure of G into a collection of O(l) chains and O(n/l) antichains, for a given parameter l. As usual a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a candidate LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to min-max matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner.

• Algorithms and Theory