Abstract: This talk will be about the problem of finding a shortest s-t path using at most h edges in edge-weighted graphs. The Bellman–Ford algorithm solves this problem in O(hm) time, where m is the number of edges. I will show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. This lower bound can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman-Ford algorithm. This is joint work with Tomasz Kociumaka (MPI Informatics).

For further information please contact: arianna.aliberti@unibocconi.it