Document Open Access Logo

Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Authors Piotr Sankowski, Karol Wegrzycki

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.56.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Piotr Sankowski
Karol Wegrzycki

Cite As Get BibTex

Piotr Sankowski and Karol Wegrzycki. Improved Distance Queries and Cycle Counting by Frobenius Normal Form. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.56

Abstract

Consider an unweighted, directed graph G with the diameter D. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time O-tilde(n^omega). The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-vector multiplication. It allows us to solve the following problems efficiently.

* All Nodes Shortest Cycles - for every node return the length of the shortest cycle containing it. We give an O-tilde(n^omega) algorithm that improves the previous O-tilde(n^((omega + 3)/2)) algorithm for unweighted digraphs.

* We show how to compute all D sets of vertices lying on cycles of length c in {1, ..., D} in randomized time O-tilde(n^omega). It improves upon an algorithm by Cygan where algorithm that computes a single set is presented.

* We present a functional improvement of distance queries for directed, unweighted graphs.

* All Pairs All Walks - we show almost optimal O-tilde(n^3) time algorithm for all walks counting problem. We improve upon the naive O(D n^omega) time algorithm.

Subject Classification

Keywords
  • Frobenius Normal Form
  • Graph Algorithms
  • All Nodes Shortest Cycles

Metrics

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

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681-1697. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.112.
  2. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377-391. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch28.
  3. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity and conditional hardness for sparse graphs. arXiv preprint arXiv:1611.07008, November 2016. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: http://dx.doi.org/10.1007/BF02523189.
  6. Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 590-598. ACM, 2007. URL: http://dx.doi.org/10.1145/1250790.1250877.
  7. Fan R. K. Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997. Google Scholar
  8. Fan R. K. Chung, V. Faber, and Thomas A. Manteuffel. An upper bound on the diameter of a graph from eigenvalues associated with its laplacian. SIAM J. Discrete Math., 7(3):443-457, 1994. URL: http://dx.doi.org/10.1137/S0895480191217776.
  9. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings. J. ACM, 62(4):28, 2015. URL: http://dx.doi.org/10.1145/2736283.
  10. David Steven Dummit and Richard M. Foote. Abstract algebra, volume 3. Wiley Hoboken, 2004. Google Scholar
  11. Wayne Eberly. Black box frobenius decompositions over small fields. In Traverso [27], pages 106-113. URL: http://dl.acm.org/citation.cfm?id=345542, URL: http://dx.doi.org/10.1145/345542.345596.
  12. Robert W. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6):345, 1962. URL: http://dx.doi.org/10.1145/367766.368168.
  13. Gudmund Skovbjerg Frandsen and Piotr Sankowski. Dynamic normal forms and dynamic characteristic polynomial. In International Colloquium on Automata, Languages, and Programming, pages 434-446. Springer Berlin Heidelberg, 2008. Google Scholar
  14. F. R. Gantmacher. The Theory of Matrices, Vol. 1. Chelsea, 1959. Google Scholar
  15. Mark Giesbrecht, Michael J. Jacobson Jr., and Arne Storjohann. Algorithms for large integer matrix problems. In Serdar Boztas and Igor E. Shparlinski, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 14th International Symposium, AAECC-14, Melbourne, Australia November 26-30, 2001, Proceedings, volume 2227 of Lecture Notes in Computer Science, pages 297-307. Springer, 2001. URL: http://dx.doi.org/10.1007/3-540-45624-4_31.
  16. Gene H. Golub and Charles F. Van Loan. Matrix computations (3. ed.). Johns Hopkins University Press, 1996. Google Scholar
  17. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303. ACM, 2014. Google Scholar
  18. Arthur Lim and Jialing Dai. On product of companion matrices. Linear Algebra and its Applications, 435(11):2921-2935, 2011. Google Scholar
  19. Thom Mulders and Arne Storjohann. Rational solutions of singular linear systems. In Traverso [27], pages 242-249. URL: http://dl.acm.org/citation.cfm?id=345542, URL: http://dx.doi.org/10.1145/345542.345644.
  20. John H. Reif and Stephen R. Tate. On dynamic algorithms for algebraic problems. J. Algorithms, 22(2):347-371, 1997. URL: http://dx.doi.org/10.1006/jagm.1995.0807.
  21. Liam Roditty and Asaf Shapira. All-pairs shortest paths with a sublinear additive error. ACM Trans. Algorithms, 7(4):45:1-45:12, September 2011. URL: http://dx.doi.org/10.1145/2000807.2000813.
  22. Raimund Seidel. On the all-pairs-shortest-path problem. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 745-749. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129784.
  23. Arne Storjohann. An O(n^3) algorithm for the frobenius normal form. In Volker Weispfenning and Barry M. Trager, editors, Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, ISSAC'98, Rostock, Germany, August 13-15, 1998, pages 101-105. ACM, 1998. URL: http://dl.acm.org/citation.cfm?id=281508, URL: http://dx.doi.org/10.1145/281508.281570.
  24. Arne Storjohann. Deterministic computation of the frobenius form. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 368-377. IEEE Computer Society, 2001. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7601, URL: http://dx.doi.org/10.1109/SFCS.2001.959911.
  25. Zhihui Tang, Ramani Duraiswami, and Nail A. Gumerov. Fast Algorithms to Compute Matrix-Vector Products for Pascal Matrices. Technical Reports from UMIACS UMIACS-TR-2004-08, 2004 25/ 2004. URL: http://drum.lib.umd.edu/handle/1903/1338.
  26. Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46(3):362-394, 1999. URL: http://dx.doi.org/10.1145/316542.316548.
  27. Carlo Traverso, editor. Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC 2000, St. Andrews, United Kingdom, August 6-10, 2000. ACM, 2000. URL: http://dl.acm.org/citation.cfm?id=345542.
  28. Stephen Warshall. A theorem on boolean matrices. J. ACM, 9(1):11-12, 1962. URL: http://dx.doi.org/10.1145/321105.321107.
  29. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664-673. ACM, 2014. URL: http://dl.acm.org/citation.cfm?id=2591796, URL: http://dx.doi.org/10.1145/2591796.2591811.
  30. Raphael Yuster. A shortest cycle for each vertex of a graph. Inf. Process. Lett., 111(21-22):1057-1061, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.07.019.
  31. Raphael Yuster and Uri Zwick. Finding even cycles even faster. In Serge Abiteboul and Eli Shamir, editors, Automata, Languages and Programming, 21st International Colloquium, ICALP94, Jerusalem, Israel, July 11-14, 1994, Proceedings, volume 820 of Lecture Notes in Computer Science, pages 532-543. Springer, 1994. URL: http://dx.doi.org/10.1007/3-540-58201-0_96.
  32. Raphael Yuster and Uri Zwick. Answering distance queries in directed graphs using fast matrix multiplication. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 389-396. IEEE Computer Society, 2005. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=10244, URL: http://dx.doi.org/10.1109/SFCS.2005.20.
  33. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. URL: http://dx.doi.org/10.1145/567112.567114.
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 About DROPS Imprint Privacy Contact