A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends

Karl Bringmann, Egor Gorbachev

In an $m$-edge host graph $G$, all triangles can be listed in time $O(m^{1.5})$ [Itai, Rodeh '78], and all $k$-cycles can be listed in time $O(m^{2-1/\lceil k/2\rceil }+t)$ whe…