Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

The all pairs shortest paths problem (APSP) in a graph with integer weights on its edges is to determine for every pair of vertices s,t the minimum weight sum over all paths from s to t in the graph (the shortest path length). APSP is a famous fundamental problem in theoretical computer science; it is also notorious because although there are several simple algorithms which solve it in O(n^3) time in n-node graphs, it is still an open problem whether there is an algorithm for APSP running in O(n^{3-eps}) time for some constant eps>0 (a truly subcubic algorithm). Besides APSP, there are several different all pairs path problems: graph transitive closure, all pairs maximum bottleneck paths (APBP), all pairs minimum nondecreasing paths (APNP)... They mainly differ from APSP in that the sum operation in the definition of path weight is replaced by a different operation (Boolean And, Min, <=). These path problems can all be seen as transitive closures of different n x n matrix products: APSP of the matrix product over the tropical semiring (min,+), APBP of the matrix product over the subtropical semiring (max, min) and graph transitive closure of the Boolean matrix product. It is known that a truly subcubic algorithm for the matrix product immediately gives a truly subcubic algorithm for the transitive closure. We show that for every (min, *) matrix product for any binary operation * over the integers there is a problem of detecting a certain type of triangle in a graph with edge weights such that there is a truly subcubic algorithm for the triangle problem iff there is a truly subcubic algorithm for the matrix product. For instance, this implies that there is a truly subcubic algorithm for APSP iff there is a truly subcubic algorithm which given a graph with integer weights on the edges determines whether the graph contains a triangle with negative weight sum. Our reduction also allows us to obtain some simple truly subcubic algorithms for APBP and APNP.