Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths

ABSTRACT

Given a directed graph with a capacity on each edge, the all-pairs bottleneck paths (APBP) problem is to determine, for all vertices s and t, the maximum flow that can be routed from s to t. For dense graphs this problem is equivalent to that of computing the (max, min)-transitive closure of a real-valued matrix. In this paper, we give a (max, min)-matrix multiplication algorithm running in time O(n^(3+ω)/2) ≤ O(n^2.688), where ω is the exponent of binary matrix multiplication. Our algorithm improves on a recent O(n^2+ω/3) ≤ O(n^2.792)- time algorithm of Vassilevska, Williams, and Yuster. Although our algorithm is slower than the best APBP algorithm on vertex capacitated graphs, running in O(n^2.575) time, it is just as efficient as the best algorithm for computing the dominance product, a problem closely related to (max, min)-matrix multiplication.

Our techniques can be extended to give subcubic algorithms for related bottleneck problems. The all-pairs bottleneck shortest paths problem (APBSP) asks for the maximum flow that can be routed along a shortest path. We give an APBSP algorithm for edge-capacitated graphs running in O(n^(3+ω)/2) time and a slightly faster O(n2.657)-time algorithm for vertex-capactitated graphs. The second algorithm significantly improves on an O(n^2.859)-time APBSP algorithm of Shapira, Yuster, and Zwick. Our APBSP algorithms make use of new hybrid products we call the distance-max-min product and dominance-distance product.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Noga Alon , Zvi Galil , Oded Margalit, On the exponent of the all pairs shortest path problem, Journal of Computer and System Sciences, v.54 n.2, p.255-262, April 1997 [doi>10.1006/jcss.1997.1388]
• 3: Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250877]
• 4: Don Coppersmith, Rectangular matrix multiplication revisited, Journal of Complexity, v.13 n.1, p.42-49, March 1997 [doi>10.1006/jcom.1997.0438]
• 5: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 6: Artur Czumaj , Mirosaw Kowaluk , Andrzej Lingas, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Theoretical Computer Science, v.380 n.1-2, p.37-46, July 2007 [doi>10.1016/j.tcs.2007.02.053]
• 7: Artur Czumaj , Andrzej Lingas, Finding a heaviest triangle is not harder than matrix multiplication, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.986-994, January 07-09, 2007, New Orleans, Louisiana
• 8: Zvi Galil , Oded Margalit, All pairs shortest distances for graphs with small integer length edges, Information and Computation, v.134 n.2, p.103-139, May 1, 1997 [doi>10.1006/inco.1997.2620]
• 9: Zvi Galil , Oded Margalit, All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, v.54 n.2, p.243-254, April 1997 [doi>10.1006/jcss.1997.1385]
• 10: Nicholas J. A. Harvey, Algebraic Structures and Algorithms for Matching and Matroid Problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.531-542, October 21-24, 2006 [doi>10.1109/FOCS.2006.8]
• 11: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476]
• 12: Jiří Matoušek, Computing dominances inEn (short communication), Information Processing Letters, v.38 n.5, p.277-278, June 14, 1991 [doi>10.1016/0020-0190(91)90071-O]
• 13: Marcin Mucha , Piotr Sankowski, Maximum Matchings via Gaussian Elimination, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.248-255, October 17-19, 2004 [doi>10.1109/FOCS.2004.40]
• 14: Marcin Mucha , Piotr Sankowski, Maximum matchings in planar graphs via gaussian elimination, Algorithmica, v.45 n.1, p.3-20, April 2006 [doi>10.1007/s00453-005-1187-5]
• 15: P. Sankowski. Weighted bipartite matching in matrix multiplication time. In Proceedings 33rd Int'l Symposium on Automata, Languages, and Programming (ICALP), pages 274--285, 2006.
• 16: Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078]
• 17: Asaf Shapira , Raphael Yuster , Uri Zwick, All-pairs bottleneck paths in vertex weighted graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.978-985, January 07-09, 2007, New Orleans, Louisiana
• 18: Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999
• 19: T. Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica, 20(3):309--318, 1998.
• 20: V. Vassilevska. Efficient Algorithms for Path Problems in Weighted Graphs. PhD thesis, Carnegie Mellon University, August 2008.
• 21: V. Vassilevska. Personal communication. 2008.
• 22: Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132550]
• 23: Virginia Vassilevska , Ryan Williams , Raphael Yuster, All-pairs bottleneck paths for general graphs in truly sub-cubic time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250876]
• 24: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms