Document Open Access Logo

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Authors Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.94.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Surya Mathialagan
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Virginia Vassilevska Williams
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Yinzhan Xu
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Mathialagan, Surya: Supported by the MIT Akamai Presidential Fellowship.
  • Vassilevska Williams, Virginia: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-2129139 and CCF-1909429, a BSF Grant BSF:2020356, a Google Research Fellowship and a Sloan Research Fellowship.
  • Xu, Yinzhan: Partially supported by NSF Grants CCF-1528078 and CCF-2129139.

Cite AsGet BibTex

Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 94:1-94:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.94

Abstract

The AP-LCA problem asks, given an n-node directed acyclic graph (DAG), to compute for every pair of vertices u and v in the DAG a lowest common ancestor (LCA) of u and v if one exists, i.e. a node that is an ancestor of both u and v but no proper descendent of it is their common ancestor. Recently [Grandoni et al. SODA'21] obtained the first sub-n^{2.5} time algorithm for AP-LCA running in O(n^{2.447}) time. Meanwhile, the only known conditional lower bound for AP-LCA is that the problem requires n^{ω-o(1)} time where ω is the matrix multiplication exponent. In this paper we study several interesting variants of AP-LCA, providing both algorithms and fine-grained lower bounds for them. The lower bounds we obtain are the first conditional lower bounds for LCA problems higher than n^{ω-o(1)}. Some of our results include: - In any DAG, we can detect all vertex pairs that have at most two LCAs and list all of their LCAs in O(n^ω) time. This algorithm extends a result of [Kowaluk and Lingas ESA'07] which showed an Õ(n^ω) time algorithm that detects all pairs with a unique LCA in a DAG and outputs their corresponding LCAs. - Listing 7 LCAs per vertex pair in DAGs requires n^{3-o(1)} time under the popular assumption that 3-uniform 5-hyperclique detection requires n^{5-o(1)} time. This is surprising since essentially cubic time is sufficient to list all LCAs (if ω = 2). - Counting the number of LCAs for every vertex pair in a DAG requires n^{3-o(1)} time under the Strong Exponential Time Hypothesis, and n^{ω(1,2,1)-o(1)} time under the 4-Clique hypothesis. This shows that the algorithm of [Echkardt, Mühling and Nowak ESA'07] for listing all LCAs for every pair of vertices is likely optimal. - Given a DAG and a vertex w_{u,v} for every vertex pair u,v, verifying whether all w_{u,v} are valid LCAs requires n^{2.5-o(1)} time assuming 3-uniform 4-hyperclique requires n^{4-o(1)} time. This defies the common intuition that verification is easier than computation since returning some LCA per vertex pair can be solved in O(n^{2.447}) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • All-Pairs Lowest Common Ancestor
  • Fine-Grained Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Loukas Georgiadis, Giuseppe F Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf. Faster algorithms for all-pairs bounded min-cuts. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, pages 7:1-7:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019. Google Scholar
  2. Hassan Aït-Kaci, Robert S. Boyer, Patrick Lincoln, and Roger Nasr. Efficient implementation of lattice operations. ACM Trans. Program. Lang. Syst., 11(1):115-146, 1989. Google Scholar
  3. Josh Alman. Limits on the universal method for matrix multiplication. In Proceedings of the 34th Computational Complexity Conference (CCC), volume 137, pages 12:1-12:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  4. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539. SIAM, 2021. Google Scholar
  5. Matthias Baumgart, Stefan Eckhardt, Jan Griebsch, Sven Kosub, and Johannes Nowak. All-pairs ancestor problems in weighted dags. In Proceedings of the First International Conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ESCAPE'07, pages 282-293. Springer-Verlag, 2007. Google Scholar
  6. Michael A. Bender, Martin Farach-Colton, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms, 57(2):75-94, 2005. Google Scholar
  7. Omer Berkman and Uzi Vishkin. Recursive star-tree parallel data structure. SIAM J. Comput., 22(2):221-242, 1993. Google Scholar
  8. Omer Berkman and Uzi Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sci., 48(2):214-230, 1994. Google Scholar
  9. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. Google Scholar
  10. Vincent Bouchitté and Jean-Xavier Rampon. On-line algorithms for orders. Theor. Comput. Sci., 175(2):225-238, 1997. Google Scholar
  11. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 307-318. IEEE, 2017. Google Scholar
  12. Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic Complexity Theory. Springer Verlag, 1997. Google Scholar
  13. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. On the Exact Complexity of Evaluating Quantified k-CNF. In Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC), volume 6478, pages 50-59. Springer, 2010. Google Scholar
  14. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. On the Exact Complexity of Evaluating Quantified k-CNF. Algorithmica, 65(4):817-827, 2013. Google Scholar
  15. Matthias Christandl, François Le Gall, Vladimir Lysikov, and Jeroen Zuiddam. Barriers for rectangular matrix multiplication. CoRR, abs/2003.03019, 2020. URL: http://arxiv.org/abs/2003.03019.
  16. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Barriers for fast matrix multiplication from irreversibility. In Proceedings of the 34th Computational Complexity Conference (CCC), volume 137, pages 26:1-26:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  17. Richard Cole and Ramesh Hariharan. Dynamic LCA queries on trees. SIAM J. Comput., 34(4):894-923, 2005. Google Scholar
  18. Artur Czumaj, Miroslaw Kowaluk, and Andrzej Lingas. Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theor. Comput. Sci., 380(1-2):37-46, 2007. Google Scholar
  19. Roland Ducournau and Michel Habib. On some algorithms for multiple inheritance in object-oriented programming. In Proceedings of ECOOP’ 87 European Conference on Object-Oriented Programming, volume 276, pages 243-252. Springer, 1987. Google Scholar
  20. Stefan Eckhardt, Andreas Michael Mühling, and Johannes Nowak. Fast lowest common ancestor computations in dags. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), volume 4698, pages 705-716, 2007. Google Scholar
  21. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci., 326(1-3):57-67, 2004. Google Scholar
  22. Johannes Fischer and Daniel H. Huson. New common ancestor problems in trees and directed acyclic graphs. Inf. Process. Lett., 110(8-9):331-335, 2010. Google Scholar
  23. Michael J. Fischer and Albert R. Meyer. Boolean matrix multiplication and transitive closure. In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (SWAT), pages 129-131. IEEE, 1971. Google Scholar
  24. Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related techniques for geometry problems. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 135-143. ACM, 1984. Google Scholar
  25. Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Lukasiewicz, Nikos Parotsidis, and Przemyslaw Uznanski. All-pairs LCA in dags: Breaking through the O(n^2.5) barrier. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 273-289. SIAM, 2021. Google Scholar
  26. Michel Habib, Marianne Huchard, and Jeremy P. Spinrad. A linear algorithm to decompose inheritance graphs into modules. Algorithmica, 13(6):573-591, 1995. Google Scholar
  27. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338-355, 1984. Google Scholar
  28. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  29. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  30. Miroslaw Kowaluk and Andrzej Lingas. LCA queries in directed acyclic graphs. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580, pages 241-248, 2005. Google Scholar
  31. Miroslaw Kowaluk and Andrzej Lingas. Unique lowest common ancestors in dags are almost as easy as matrix multiplication. In Proceedings of the 15th Annual European Symposium (ESA), volume 4698, pages 265-274. Springer, 2007. Google Scholar
  32. Mirosław Kowaluk, Andrzej Lingas, and Johannes Nowak. A path cover technique for lcas in dags. In Scandinavian Workshop on Algorithm Theory (SWAT), pages 222-233. Springer, 2008. Google Scholar
  33. Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1029-1046. SIAM, 2018. Google Scholar
  34. Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 53:1-53:18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. Google Scholar
  35. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1236-1252. SIAM, 2018. Google Scholar
  36. Matti Nykänen and Esko Ukkonen. Finding lowest common ancestors in arbitrarily directed trees. Inf. Process. Lett., 50(6):307-310, 1994. Google Scholar
  37. Baruch Schieber and Uzi Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM J. Comput., 17(6):1253-1262, 1988. Google Scholar
  38. Robert Endre Tarjan. Applications of path compression on balanced trees. J. ACM, 26(4):690-715, 1979. Google Scholar
  39. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1-27:38, 2018. Google Scholar
  40. Zhaofang Wen. New algorithms for the LCA problem and the binary tree reconstruction problem. Inf. Process. Lett., 51(1):11-16, 1994. Google Scholar
  41. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact