English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Despite persistent efforts, there is no known technique for obtainingunconditional super-linear lower bounds for the computational complexity of theproblems in P. Vassilevska Williams and Williams introduce a fruitful approachto advance a better understanding of the computational complexity of theproblems in P. In particular, they consider All Pairs Shortest Paths (APSP) andother fundamental problems such as checking whether a matrix defines a metric,verifying the correctness of a matrix product, and detecting a negativetriangle in a graph. Abboud, Grandoni, and Vassilevska Williams studywell-known graph centrality problems such as Radius, Median, etc., and make aconnection between their computational complexity to that of two fundamentalproblems, namely APSP and Diameter. They show any algorithm with subcubicrunning time for these centrality problems, implies a subcubic algorithm foreither APSP or Diameter. In this paper, we define vertex versions for thesecentrality 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 areequivalent under subcubic reduction. One of the results of this paper is APSPand CoDiameter, which is the complementary version of Diameter, are equivalent.Moreover, for some of the problems in this set, we show that they areequivalent to their complementary versions. Considering the slight differencebetween a problem and its complementary version, these equivalences give us theimpression that every problem has such a property, and thus APSP and Diameterare equivalent. This paper is a step forward in showing a subcubic equivalencebetween APSP and Diameter, and we hope that the approach introduced in ourpaper can be helpful to make this breakthrough happen.

Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems