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 λ satisfies the equation ω(1,λ,1)=1+2λ and ω(1,λ,1) is the exponent of the multiplication of an n×nλ matrix by an nλ×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 h≤nα, where α≈0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n×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.