Our first main result is a fine-grained self-reduction for Triangle from worst-case \(\sqrt{n}\) -degree graphs to graphs with few \(k^{\prime }\) -cycles for all \(4 \le k^{\prime } \le k\) .
For concreteness, consider the All-Edge version where we want to report for each of the \(m=O(n^{1.5})\)  edges in the graph whether it is in a triangle.
This problem is known to require \(n^{2-o(1)}\)  time, under the 3-SUM Conjecture [1]}, [2]} or under the APSP Conjecture [3]}, and this holds even for graphs of maximum degree \(\sqrt{n}\) . Thus it is a very plausible conjecture that \(n^{2-o(1)}\)  is required. (See Theorem REF  and the discussion in Section .)
A worst-case input graph to this problem might have up to \(n^{k/2+1/2}\)  \(k\) -cycles.
Given such a graph, for a sufficiently small constant \(\alpha > 0\)  depending on \(k\) , the following theorem constructs many subgraphs such that: (1) solving All-Edge-Triangle on all of these subgraphs suffices to solve the original problem, (2) the total number of edges in all these subgraphs is subquadratic \(n^{2-\Omega (1)}\) , and (3) the total number of \(k\) -cycles in all these subgraphs is subquadratic \(n^{2-\Omega (1)}\) .
The latter implies that a linear-time algorithm for All-Edge-Triangle in graphs with few short cycles implies a subquadratic algorithm for the starting problem and refutes the popular conjectures.
