Finding least common ancestors in directed acyclic graphs (Q2768390)

The least common ancestor (lca) problem for trees, see e.g. \textit{B. Schieber} and \textit{U. Vishkin} [SIAM J. Comput. 17, No. 6, 1253-1262 (1988; Zbl 0669.68049)], is generalised to directed acyclic graphs (dags) and partially ordered sets, respectively. In a rooted tree any two nodes have a unique lca. In this more general setting the number of lcas may vary. The authors relate the lca problem for dags to the all pairs shortest path and transitive closure problems which can be solved in time \(O(n^{\alpha})\), the time required for matrix multiplication. More precisely, for all pairs of nodes in a dag the existence of an lca can be decided in time \(O(n^{\alpha})\) and an lca can be found in time \(O(n^{(\alpha+3)/2})\). The time required for computing the transitive closure of a dag is a lower bound for the latter problem. The same bounds apply to the all pairs longest path problem on unweighted dags. Finally, some experimental data is presented.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].