Warm-Starting All-Pairs Shortest Paths with Predictions

Adam Polak, Jonas Schmidt

One of the three key hypotheses of fine-grained complexity asserts that computing All-Pairs Shortest Paths (APSP) requires cubic time, up to subpolynomial factors, in the worst cas…