A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms

In a seminal work, Chiba and Nishizeki SIAM J. Comput. `85 developed subgraph listing algorithms for triangles, 4-cycle and k-cliques, where k 3. The runtimes of their algorithms are parameterized by the number of edges m and the arboricity of a graph. The arboricity of a graph is the minimum number of spanning forests required to cover it. Their work introduces: * A triangle listing algorithm that runs in O (m) time. * An output-sensitive 4-Cycle-Listing algorithm that lists all 4-cycles in O (m + t) time, where t is the number of 4-cycles in the graph. * A k-Clique-Listing algorithm that runs in O (m^k-2) time, for k 4. Despite the widespread use of these algorithms in practice, no improvements have been made over them in the past few decades. Therefore, recent work has gone into studying lower bounds for subgraph listing problems. The works of Kopelowitz, Pettie and Porat SODA `16 and Vassilevska W. and Xu FOCS `20 showed that the triangle-listing algorithm of Chiba and Nishizeki is optimal under the 3SUM and APSP hypotheses respectively. However, it remained open whether the remaining algorithms were optimal. In this note, we show that in fact all the above algorithms are optimal under popular hardness conjectures. First, we show that the 4-Cycle-Listing algorithm is tight under the 3SUM hypothesis following the techniques of Jin and Xu STOC `23, and Abboud, Bringmann and Fishcher STOC `23. Additionally, we show that the k-Clique-Listing algorithm is essentially tight under the exact k-clique hypothesis by following the techniques of Dalirooyfard, Mathialagan, Vassilevska W. and Xu STOC `24. These hardness results hold even when the number of 4-cycles or k-cliques in the graph is small.