Document Open Access Logo

New Parameterized Algorithms for APSP in Directed Graphs

Authors Ely Porat, Eduard Shahbazian, Roei Tov

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.72.pdf
  • Filesize: 492 kB
  • 13 pages

Document Identifiers

Author Details

Ely Porat
Eduard Shahbazian
Roei Tov

Cite As Get BibTex

Ely Porat, Eduard Shahbazian, and Roei Tov. New Parameterized Algorithms for APSP in Directed Graphs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.72

Abstract

All Pairs Shortest Path (APSP) is a classic problem in graph theory. While for general weighted graphs there is no algorithm that computes APSP in O(n^{3-epsilon}) time (epsilon > 0), by using fast matrix multiplication algorithms, we can compute APSP in O(n^{omega}*log(n)) time (omega < 2.373) for undirected unweighted  graphs, and in O(n^{2.5302}) time for directed unweighted graphs. In the current state of matters, there is a substantial gap between the upper bounds of the problem for undirected and directed graphs, and for a long time, it is remained an important open question whether it is possible to close this gap.

In this paper we introduce a new parameter that measures the symmetry of directed graphs (i.e. their closeness to undirected graphs), and obtain a new parameterized APSP algorithm for directed unweighted graphs, that generalizes Seidel's O(n^{omega}*log(n)) time algorithm for undirected unweighted graphs. Given a directed unweighted graph G, unless it is highly asymmetric, our algorithms can compute APSP in o(n^{2.5}) time for G, providing for such graphs a faster APSP algorithm than the state-of-the-art algorithms for the problem.

Subject Classification

Keywords
  • Graphs
  • distances
  • APSP
  • fast matrix multiplication

Metrics

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

References

  1. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. URL: http://dx.doi.org/10.1137/S0097539796303421.
  2. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 569-575, 1991. Google Scholar
  3. Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput., 39(5):2075-2089, 2010. URL: http://dx.doi.org/10.1137/08071990X.
  4. Timothy M. Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1246-1255, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch87.
  5. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. J. Symb. Comput., 9(3):251-280, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80013-2.
  6. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  7. Michael L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5(1):83-89, 1976. URL: http://dx.doi.org/10.1137/0205006.
  8. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. URL: http://dx.doi.org/10.1145/28869.28874.
  9. Zvi Galil and Oded Margalit. All pairs shortest distances for graphs with small integer length edges. Inf. Comput., 134(2):103-139, 1997. URL: http://dx.doi.org/10.1006/inco.1997.2620.
  10. François Le Gall. Faster algorithms for rectangular matrix multiplication. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 514-523, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.80.
  11. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303, 2014. URL: http://dx.doi.org/10.1145/2608628.2608664.
  12. Yijie Han. Improved algorithm for all pairs shortest paths. Inf. Process. Lett., 91(5):245-250, 2004. URL: http://dx.doi.org/10.1016/j.ipl.2004.05.006.
  13. Yijie Han. An O n ^3(log log n /log n )^5/4) time algorithm for all pairs shortest path. Algorithmica, 51(4):428-434, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9063-0.
  14. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413-423, 1978. URL: http://dx.doi.org/10.1137/0207033.
  15. Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1-13, 1977. URL: http://dx.doi.org/10.1145/321992.321993.
  16. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47-74, 2004. URL: http://dx.doi.org/10.1016/S0304-3975(03)00402-X.
  17. Liam Roditty and Roei Tov. Approximating the girth. ACM Transactions on Algorithms, 9(2):15, 2013. URL: http://dx.doi.org/10.1145/2438645.2438647.
  18. Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 180-189, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.27.
  19. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 515-524, 2013. URL: http://dx.doi.org/10.1145/2488608.2488673.
  20. Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1078.
  21. Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights. In 40th Annual Symposium on Foundations of Computer Science, FOCS'99, 17-18 October, 1999, New York, NY, USA, pages 605-615, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814635.
  22. Tadao Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica, 20(3):309-318, 1998. URL: http://dx.doi.org/10.1007/PL00009198.
  23. Tadao Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In Computing and Combinatorics, 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings, pages 278-289, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27798-9_31.
  24. Mikkel Thorup. Floats, integers, and single source shortest paths. J. Algorithms, 35(2):189-201, 2000. URL: http://dx.doi.org/10.1006/jagm.2000.1080.
  25. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645-654, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  26. 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.
  27. Uri Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings, pages 921-932, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30551-4_78.
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