Tight Hardness for Shortest Cycles and Paths in Sparse Graphs

Andrea Lincoln, Virginia Vassilevska Williams, Ryan Williams

Fine-grained reductions have established equivalences between many core problems with $\tilde{O}(n^3)$-time algorithms on $n$-node weighted graphs, such as Shortest Cycle, All-Pair…