A path cover technique for LCAs in dags.

*(English)*Zbl 1155.68476
Gudmundsson, Joachim (ed.), Algorithm theory – SWAT 2008. 11th Scandinavian workshop on algorithm theory, Gothenburg, Sweden, July 2–4, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69900-2/pbk). Lecture Notes in Computer Science 5124, 222-233 (2008).

Summary: We develop a path cover technique to solve lowest common ancestor (LCA for short) problems in a directed acyclic graph (dag).

Our method yields improved upper bounds for two recently studied problem variants, computing one (representative) LCA for all pairs of vertices and computing all LCAs for all pairs of vertices. The bounds are expressed in terms of the number \(n\) of vertices and the so called width \(w(G)\) of the input dag \(G\). For the first problem we achieve \(\widetilde{O}(n^2 w(G))\) time, which improves the upper bound of [M. Kowaluk and A. Lingas, “Unique lowest common ancestors in dags are almost as easy as matrix multiplication”, Lect. Notes Comput. Sci. 4698, 265–274 (2007; Zbl 1151.68429)] for dags with \(w(G) = O( n ^{0.376 - \delta })\) for a constant \(\delta > 0\). For the second problem our \(\widetilde{O}(n^2 w(G)^2)\) upper time bound subsumes the \(O(n ^{3.334})\) bound established in [S. Eckhardt, A. M. Mühling and J. Nowak, “Fast lowest common ancestor computations in dags”, Lect. Notes Comput. Sci. 4698, 705–716 (2007; Zbl 1151.68736)] for \(w(G) = O(n ^{0.667 - \delta })\).

As a second major result we show how to combine the path cover technique with LCA solutions for dags with small depth. Our algorithm attains the best known upper time bound for this problem of \(O(n ^{2.575})\). However, most notably, the algorithm performs better on a vast amount of input dags, i.e. dags that do not have an almost linear-sized subdag of extremely regular structure.

Finally, we apply our technique to improve the general upper time bounds on the worst case time complexity for the problem of reporting LCAs for each triple of vertices recently established by R. Yuster [“All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time”, Theor. Comput. Sci. 396, No. 1–3, 145–150 (2008; Zbl 1140.68054)].

For the entire collection see [Zbl 1139.68004].

Our method yields improved upper bounds for two recently studied problem variants, computing one (representative) LCA for all pairs of vertices and computing all LCAs for all pairs of vertices. The bounds are expressed in terms of the number \(n\) of vertices and the so called width \(w(G)\) of the input dag \(G\). For the first problem we achieve \(\widetilde{O}(n^2 w(G))\) time, which improves the upper bound of [M. Kowaluk and A. Lingas, “Unique lowest common ancestors in dags are almost as easy as matrix multiplication”, Lect. Notes Comput. Sci. 4698, 265–274 (2007; Zbl 1151.68429)] for dags with \(w(G) = O( n ^{0.376 - \delta })\) for a constant \(\delta > 0\). For the second problem our \(\widetilde{O}(n^2 w(G)^2)\) upper time bound subsumes the \(O(n ^{3.334})\) bound established in [S. Eckhardt, A. M. Mühling and J. Nowak, “Fast lowest common ancestor computations in dags”, Lect. Notes Comput. Sci. 4698, 705–716 (2007; Zbl 1151.68736)] for \(w(G) = O(n ^{0.667 - \delta })\).

As a second major result we show how to combine the path cover technique with LCA solutions for dags with small depth. Our algorithm attains the best known upper time bound for this problem of \(O(n ^{2.575})\). However, most notably, the algorithm performs better on a vast amount of input dags, i.e. dags that do not have an almost linear-sized subdag of extremely regular structure.

Finally, we apply our technique to improve the general upper time bounds on the worst case time complexity for the problem of reporting LCAs for each triple of vertices recently established by R. Yuster [“All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time”, Theor. Comput. Sci. 396, No. 1–3, 145–150 (2008; Zbl 1140.68054)].

For the entire collection see [Zbl 1139.68004].