Faster algorithms for finding lowest common ancestors in directed acyclic graphs.

*(English)*Zbl 1118.68102Summary: 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(n^{2+\lambda })\), where \(\lambda\) satisfies the equation \(\omega (1,\lambda,1) = 1 + 2\lambda\) and \(\omega (1,\lambda ,1)\) is the exponent of the multiplication of an \(n\times n^{\lambda }\) matrix by an \(n^{\lambda }\times n\) matrix. By the currently best known bounds on \(\omega (1,\lambda ,1)\), the running time of our algorithm is \(O(n^{2.575})\). Our algorithm improves the previously known \(O(n^{2.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\leq n^{\alpha }\), where \(\alpha \approx 0.294\), our algorithm runs in a time that is asymptotically the same as that required for multiplying two \(n\times n\) matrices, that is, \(O(n^{\omega })\); we also prove that this running time is optimal even for dags of depth 1. For dags with depth \(h>n^{\alpha }\), the running time of our algorithm is at most \(O(n^{\omega}\cdot h^{0.468})\). This algorithm is faster than our algorithm for arbitrary dags for all values of \(h\leq n^{0.42}\).

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(n^{2+\lambda })\), where \(\lambda\) satisfies the equation \(\omega (1,\lambda,1) = 1 + 2\lambda\) and \(\omega (1,\lambda ,1)\) is the exponent of the multiplication of an \(n\times n^{\lambda }\) matrix by an \(n^{\lambda }\times n\) matrix. By the currently best known bounds on \(\omega (1,\lambda ,1)\), the running time of our algorithm is \(O(n^{2.575})\). Our algorithm improves the previously known \(O(n^{2.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\leq n^{\alpha }\), where \(\alpha \approx 0.294\), our algorithm runs in a time that is asymptotically the same as that required for multiplying two \(n\times n\) matrices, that is, \(O(n^{\omega })\); we also prove that this running time is optimal even for dags of depth 1. For dags with depth \(h>n^{\alpha }\), the running time of our algorithm is at most \(O(n^{\omega}\cdot h^{0.468})\). This algorithm is faster than our algorithm for arbitrary dags for all values of \(h\leq n^{0.42}\).

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

05C20 | Directed graphs (digraphs), tournaments |

05C38 | Paths and cycles |

05C85 | Graph algorithms (graph-theoretic aspects) |

68W40 | Analysis of algorithms |

PDF
BibTeX
XML
Cite

\textit{A. Czumaj} et al., Theor. Comput. Sci. 380, No. 1--2, 37--46 (2007; Zbl 1118.68102)

Full Text:
DOI

##### References:

[1] | Alon, N.; Naor, M., Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16, 434-449, (1996) · Zbl 0857.68055 |

[2] | A. Becker, D. Geiger, A.A. Schaeffer, Automatic selection of loop breakers for genetic linkage analysis |

[3] | M.A. Bender, M. Farach-Colton, The LCA problem revisited, in: Proc. 4th Latin American Symposium on Theoretical Informatics, LATIN’00, 2000, pp. 88-93 · Zbl 0959.68133 |

[4] | M.A. Bender, G. Pemmasani, S. Skiena, P. Sumazin, Finding least common ancestors in directed acyclic graphs, in: Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’01, 2001, pp. 845-853 · Zbl 0984.05041 |

[5] | Cole, R.; Hariharan, R., Dynamic LCA queries in trees, SIAM journal on computing, 34, 4, 894-923, (2005) · Zbl 1075.68019 |

[6] | Coppersmith, D., Rectangular matrix multiplication revisited, Journal of symbolic computation, 13, 42-49, (1997) · Zbl 0872.68052 |

[7] | Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progression, Journal of symbolic computation, 9, 251-290, (1990) · Zbl 0702.65046 |

[8] | Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C., Introduction to algorithms, (2001), McGraw-Hill Book Company Boston, MA · Zbl 1047.68161 |

[9] | Cottingham, R.W.; Idury, R.M.; Shäffer, A.A., Genetic linkage computations, American journal of human genetics, 53, 252-263, (1993) |

[10] | A. Czumaj, A. Lingas, Improved algorithms for the all-pairs lowest common ancestor problem in directed acyclic graphs, 2005, Manuscript |

[11] | Galil, Z.; Margalit, O., Witnesses for Boolean matrix multiplication and for transitive closure, Journal of complexity, 9, 201-221, (1993) · Zbl 0785.65053 |

[12] | Harel, D.; Tarjan, R.E., Fast algorithms for finding nearest common ancestors, SIAM journal on computing, 13, 2, 338-355, (1984) · Zbl 0535.68022 |

[13] | Huang, X.; Pan, V.Y., Fast rectangular matrix multiplications and applications, Journal of complexity, 14, 257-299, (1998) · Zbl 0919.65030 |

[14] | M. Kowaluk, A. Lingas, LCA queries in directed acyclic graphs, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, ICALP’05, 2005, pp. 241-248 · Zbl 1082.68593 |

[15] | Nykänen, M.; Ukkonen, E., Finding lowest common ancestors in arbitrarily directed trees, Information processing letters, 50, 6, 307-310, (1994) · Zbl 0810.68071 |

[16] | Shäffer, A.A.; Gupta, S.K.; Shriram, K.; Cottingham, R.W., Avoiding recomputation in linkage analysis, Human heredity, 44, 225-237, (1994) |

[17] | Tarjan, R.E., Applications of path compression on balanced trees, Journal of the ACM, 26, 4, 690-715, (1979) · Zbl 0413.68063 |

[18] | Zwick, U., All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM, 49, 3, 289-317, (2002) · Zbl 1326.05157 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.