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