Can I read Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems on EtoBox?

Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems by Boroujeni, Mahdi; Dehghani, Sina; Ehsani, Soheil; HajiAghayi, MohammadTaghi; Seddighin, Saeed is a scholarly article available to read on EtoBox.

What is Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems about?

Despite persistent efforts, there is no known technique for obtaining unconditional super-linear lower bounds for the computational complexity of the problems in P. Vassilevska Williams and Williams introduce a fruitful approach to advance a better understanding of the computational complexity of the problems in P. In particular, they consider All Pairs Shortest Paths (APSP) and other fundamental problems such as checking whether a matrix defines a metric, verifying the correctness of a matrix product, and detecting a negative triangle in a graph. Abboud, Grandoni, and Vassilevska Williams study well-known graph centrality problems such as Radius, Median, etc., and make a connection between their computational complexity to that of two fundamental problems, namely APSP and Diameter. They show any algorithm with subcubic running time for these centrality problems, implies a subcubic algorithm for either APSP or Diameter. In this paper, we define vertex versions for these centrality problems and based on that we introduce new complementary problems. The main open problem of Abboud et al. is whether or not APSP and Diameter are equivalent under subcubic reduction. One of the results o

Author

Boroujeni, Mahdi; Dehghani, Sina; Ehsani, Soheil; HajiAghayi, MohammadTaghi; Seddighin, Saeed

Published

2019

Language

EN