In the paper "Subcubic equivalences between graph centrality problems, APSP and diameter", it is shown that the all pairs shortest path problem (APSP) and the problem of computing the betweenness centrality for a vertex (BET) is equivalent under subcubic reduction. That is, APSP has a truly subcubic algorithm, if and only if BET has a truly subcubic algorithm.

In the reduction from BET to APSP, it is assumed that shortest paths are unique. I wonder why this assumption makes sense. Does it mean that if this assumption does not hold, then BET and APSP are not equivalent any more?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.