pdf icon
Volume 5 (2009) Article 9 pp. 173-189
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time
Received: July 25, 2008
Published: September 13, 2009
Download article from ToC site:
[PDF (265K)] [PS (883K)] [Source ZIP]
Keywords: bottleneck path, maximum capacity path, matrix multiplication, subcubic time
ACM Classification: G.2.2, F.2.2
AMS Classification: 05C85, 68R10

Abstract: [Plain Text Version]

$ \newcommand{\R}{{\mathbb R}} $

In the all pairs bottleneck paths (APBP) problem, one is given a directed graph with real weights on its edges. Viewing the weights as capacities, one is asked to determine, for all pairs $(s,t)$ of vertices, the maximum amount of flow that can be routed along a single path from $s$ to $t$. The APBP problem was first studied in operations research, shortly after the introduction of maximum flows and all pairs shortest paths.

We present the first truly subcubic algorithm for APBP in general dense graphs. In particular, we give a procedure for computing the $(\max,\min)$-product of two arbitrary matrices over $\R \cup \{\infty,-\infty\}$ in $O(n^{2+\omega/3}) \leq O(n^{2.792})$ time, where $n$ is the number of vertices and $\omega$ is the exponent for matrix multiplication over rings. Max-min products can be used to compute the maximum bottleneck values for all pairs of vertices together with a “successor matrix” from which one can extract an explicit maximum bottleneck path for any pair of vertices in time linear in the length of the path.