research-article

Subcubic Equivalences Between Path, Matrix, and Triangle Problems

Authors:

Virginia Vassilevska Williams,

R. Ryan WilliamsAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 5

Article No.: 27, Pages 1 - 38

https://doi.org/10.1145/3186893

Published: 29 August 2018 Publication History

Get Access

Abstract

We say an algorithm on n × n matrices with integer entries in [−M,M] (or n-node graphs with edge weights from [−M,M]) is truly subcubic if it runs in O(n^{3 − δ} ċ poly(log M)) time for some δ > 0. We define a notion of subcubic reducibility and show that many important problems on graphs and matrices solvable in O(n³) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do:

•The all-pairs shortest paths problem on weighted digraphs (APSP).

•Detecting if a weighted graph has a triangle of negative total edge weight.

•Listing up to n^2.99 negative triangles in an edge-weighted graph.

•Finding a minimum weight cycle in a graph of non-negative edge weights.

•The replacement paths problem on weighted digraphs.

•Finding the second shortest simple path between two nodes in a weighted digraph.

•Checking whether a given matrix defines a metric.

•Verifying the correctness of a matrix product over the (min, +)-semiring.

•Finding a maximum subarray in a given matrix.

Therefore, if APSP cannot be solved in n^3−ε time for any ε > 0, then many other problems also need essentially cubic time. In fact, we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms.

Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR,AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two improved BMM algorithms: a derandomization of the combinatorial BMM algorithm of Bansal and Williams (FOCS’09), and an improved quantum algorithm for BMM.

References

[1]

Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. 2015. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1681--1697.

Abstract

References

Cited By

Index Terms

Recommendations

Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter

Subcubic Equivalences between Path, Matrix and Triangle Problems

A Shortest Path Algorithm for Real-Weighted Undirected Graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

HTML Format

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations