Back to TGINF

# Tight Hardness for Shortest Cycles and Paths in Sparse Graphs

Speaker: Andrea
Title: Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Date: 30 Apr 2018 5:30pm-7:00pm
Location: Pierce 320
Food: Chinese food

Abstract: 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-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also have $\tilde{O}(mn)$-time algorithms on $m$-edge $n$-node weighted graphs, and such algorithms have wider applicability. Are these mn$bounds optimal when m « n^2? Starting from the hypothesis that the minimum weight$(2\ell +1)$-Clique problem in edge weighted graphs requires$n^{2\ell+1-o(1)}$time, we prove that for all sparsities of the form$m = \Theta(n^{1+1/\ell })$, there is no$O(n^2 + mn^{1- \epsilon })$time algorithm for$\epsilon >0$for any of the below problems Minimum Weight$(2\ell +1)$-Cycle in a directed weighted graph, Shortest Cycle in a directed weighted graph, APSP in a directed or undirected weighted graph, Radius (or Eccentricities) in a directed or undirected weighted graph, Wiener index of a directed or undirected weighted graph, Replacement Paths in a directed weighted graph, Second Shortest Path in a directed weighted graph, Betweenness Centrality of a given node in a directed weighted graph. That is, we prove hardness for a variety of sparse graph problems from the hardness of a dense graph problem. Our results also lead to new conditional lower bounds from several related hypothesis for unweighted sparse graph problems including$k\$-cycle, shortest cycle, Radius, Wiener index and APSP.