Finding least common ancestors in directed acyclic graphs
Michael A. Bender, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin · 2001
One of the fundamental algorithmic problems on trees is how to find the least common ancestor (LCA) of a given pair of nodes. The LCA of nodes u and v in a tree is an ancestor of u and v that is located farthest from the root. The LCA problem is stated as follows: Given a rooted tree T, how can we preprocess T to answer LCA queries quickly on any pair of nodes? The LCA problem has been studied intensively both because it is inherently beautiful and because fast algorithms for the LCA problem can be used to solve other algorithmic problems. However, many similar combinatorial problems cannot be solved using the tree LCA algorithmic machinery because the ancestor queries are on more complicated directed structures. Examples of such combinatorial problems include preprocessing arbitrarily (unrooted) directed trees [NU94], computing the LCA on lattices (used to represent inheritance graphs) [AKBLN89], and finding modular coverings in inheritance graphs [DH87, HHS95]. In this paper we introduce a natural extension to all of these LCA problems. We develop algorithms for efficiently answering least common ancestor queries on directed acyclic graphs (DAGs). An LCA w of nodes u and v in a DAG is an ancestor of both u and v where w has no descendants that are ancestors of both u and v. (See Definitions 2.1 and 2.2.) We present an o(n 3) preprocessing algorithm for answering least common ancestor queries on DAGs in constant time. We then initiate an experimental study of new and existing LCA algorithms on rooted trees and DAGs. Least common ancestor queries on general DAGs appear in a variety of applications, including the following: