All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier

In this paper, we answer this question affirmatively: in particular, we present an Õ (n^2.447) (Õ (n^{7/3}) for ω=2) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of G into a collection of O(ℓ) chains and O(n/ℓ) antichains, for a given parameter ℓ. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a \emph{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.

Joint work with Fabrizio Grandoni, Giuseppe F. Italiano, Nikos Parotsidis, Przemysław Uznański. Appeared on SODA 2021.