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

Yael Kirkpatrick, Surya Mathialagan

In a seminal work, Chiba and Nishizeki [SIAM J. Comput. `85] developed subgraph listing algorithms for triangles, 4-cycle and $k$-cliques, where $k\ge 3.$ The runtimes of their a…