Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Connects several graph centrality problems (like closeness and betweenness measures) to All-Pairs Shortest Paths (APSP) and Diameter computation by showing subcubic-time equivalences. Uses reductions between these problems to argue that improving running times below n^3 for one implies similar improvements for the others, so breakthroughs for APSP or Diameter would transfer to centrality measures.
AI-written summary · about