Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication

摘要

We consider the problem of determining for each pair of vertices of a directed acyclic graph (dag) on n vertices whether or not it has a unique lowest common ancestor, and if so, finding such an ancestor. We show that this problem can be solved in time O(n~ω log n), where ω < 2.376 is the exponent of the fastest known algorithm for multiplication of two n × n matrices. We show also that the problem of determining a lowest common ancestor for each pair of vertices of an arbitrary dag on n vertices is solvable in time 1~O(n~2p + n~ω), where p is the minimum number of directed paths covering the vertices of the dag. With the help of random bits, we can solve the latter problem in time O(n~2p).