Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu

Introduction

In the field of Fine-Grained Complexity (FGC), researchers aim to determine the precise time complexity of fundamental polynomial-time problems. While many problems are known to be solvable in "sub-cubic" or "sub-quadratic" time, several structural mysteries have persisted. Specifically, researchers have sought to understand the performance gap between directed and undirected All-Pairs Shortest Paths (APSP), the relationship between detecting a solution and counting all solutions, and the connection between weighted and unweighted problem variants.

This paper provides a unified framework to address these questions by combining two classic algorithmic techniques: Fredman’s trick and Matoušek’s dominance product. The authors demonstrate that for several core problems, counting solutions is no harder than detecting them, and they establish new conditional lower bounds for unweighted directed APSP.

Algorithmic Framework

The primary contribution of this work lies in the synthesis of Fredman’s trick and Matoušek’s dominance product to handle "many-witnesses" scenarios—situations where a problem has so many solutions that traditional listing methods are inefficient.

Fredman’s Trick

Fredman’s trick is an algebraic rearrangement used to simplify comparisons. For instance, to determine if $a + b \le c + d$, one can rearrange the terms to $a - c \le d - b$. This separation allows terms from different sets or matrices to be grouped together, facilitating more efficient processing through sorting or fast matrix operations.

Matoušek’s Dominance Product

Matoušek’s dominance product is an algorithm designed to compute the number of indices $k$ such that $A[i, k] \le B[k, j]$ for two matrices $A$ and $B$. By leveraging fast matrix multiplication, this technique allows for the efficient counting of pairs that satisfy specific inequality constraints.

Triangle Decomposition Theorem

The authors also introduce a Triangle Decomposition Theorem. This theorem serves as a simpler, more algorithmic alternative to the famous Balog–Szemerédi–Gowers (BSG) Theorem from additive combinatorics. It provides a structural way to decompose sets of triples, which is essential for analyzing problems like 3SUM and Triangle Detection.

Equivalence of Counting and Detection

A significant finding of this research is that for several "staple" problems in FGC—including 3SUM, Min-Plus Product, and Exact Triangle—the decision (detection) version and the counting version are computationally equivalent in the sub-quadratic or sub-cubic regime.

In many areas of complexity theory, such as those involving #P-completeness, counting is significantly more difficult than detection. However, this work shows that if one can solve the detection version of 3SUM in $O(n^{2-\epsilon})$ time, one can also solve the counting version (#3SUM) in roughly the same time. This suggests that the "counting" variants of these problems do not reside in a harder complexity class within the fine-grained landscape.

The Hardness of Directed APSP

One of the most persistent questions in graph algorithms is why unweighted undirected APSP can be solved in $O(n^\omega)$ time (where $\omega \approx 2.37$), while the directed version appears to require significantly more time (approximately $O(n^{2.53})$).

The authors provide a theoretical explanation for this "Directed Gap." By reducing weighted APSP to unweighted directed APSP, they demonstrate that the directed version is inherently tied to the complexity of the weighted version. Under the Strong APSP Hypothesis—which posits that weighted APSP requires $n^{3-o(1)}$ time—the authors prove that unweighted directed APSP must require at least $n^{7/3-o(1)}$ time (assuming $\omega = 2$). This provides the first formal justification for why directed graphs are fundamentally more difficult for shortest-path computations.

Key Results and Improvements

The paper establishes several new bounds and algorithmic improvements:

  • New Lower Bounds: Under the Strong APSP Hypothesis, the Min-Witness Product requires $n^{11/5-o(1)}$ time.
  • Counting APSP: The authors present a new deterministic algorithm for exactly counting shortest paths in weighted graphs (#APSP) in $O(n^{3.83})$ time, a notable improvement over the textbook $O(n^4)$ approach.
  • 3SUM Queries: For 3SUM in preprocessed universes, the authors improve query times to $O(n^{11/6})$, down from the previous $O(n^{13/7})$.

Conclusion and Future Work

By bridging the gap between weighted and unweighted problems, this work clarifies the fine-grained landscape of several fundamental algorithms. While the results are conditional on hypotheses like the Strong APSP Hypothesis, they provide a rigorous framework for understanding why certain problems remain resistant to "truly sub-cubic" solutions.

Future work remains to determine if similar counting-detection equivalences exist for other core problems, such as Orthogonal Vectors (OV) or CNF-SAT. Additionally, while the theoretical exponents have been improved, the practical implementation of these algorithms remains a challenge due to the large hidden constants associated with fast matrix multiplication.

Summary updated

Abstract

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou\v{s}ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights in $\{1, 2, \ldots, n\}$ requires $n^{3-o(1)}$ time (when $\omega=2$), we show a variety of conditional lower bounds, including an $n^{7/3-o(1)}$ lower bound for unweighted directed APSP and an $n^{2.2-o(1)}$ lower bound for computing the Minimum Witness Product between two $n \times n$ Boolean matrices, even if $\omega=2$, improving upon their trivial $n^2$ lower bounds. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when $\omega = 2$), if unweighted directed APSP requires $n^{2.5-o(1)}$ time, then Minimum Witness Product requires $n^{7/3-o(1)}$ time. - We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version. - We obtain new algorithms using new variants of the Balog-Szemer\'edi-Gowers theorem from additive combinatorics. For example, we get an $O(n^{3.83})$ time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook $\widetilde{O}(n^{4})$ time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in $\{1, 2, \ldots, n\}^d$.
BibTeX
@inproceedings{chan2023fredman,
  author = {Timothy M. Chan and Virginia Vassilevska Williams and Yinzhan Xu},
  title = {{Fredman's Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More}},
  booktitle = {STOC},
  year = {2023},
  url = {https://openreview.net/forum?id=EBDmwYLeuM},
}
Figure