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

In an m-edge host graph G, all triangles can be listed in time O(m1.5) [Itai, Rodeh ’78], and all k-cycles can be listed in time O(m2−1/⌈ k/2 ⌉ + t) where t is the output size [Alon, Yuster, Zwick ’97]. These classic results also hold for the colored problem variant, where the nodes of the host graph G are colored by nodes in the pattern graph H, and we are only interested in subgraphs of G that are isomorphic to the pattern H and respect the colors. We study the problem of listing all H-subgraphs in the colored setting, for fixed pattern graphs H. As our main result, we determine all pattern graphs H such that all H-subgraphs can be listed in subquadratic time O(m2−ε + t), where t is the output size. Moreover, for each such subquadratic pattern H we determine the smallest exponent c(H) such that all H-subgraphs can be listed in time O(mc(H) + t). This is a vast generalization of the classic results on triangles and cycles. In particular, it answers an open problem from the database community [Joglekar, Ré ’18]. We also show the same results for two related problems: finding an H-subgraph of minimum total edge-weight in time O(mc(H)), and enumerating all H-subgraphs in O(mc(H)) preprocessing time and constant delay. Again we determine all pattern graphs H that have complexity c(H) < 2, and for each such subquadratic pattern we determine the optimal complexity c(H). To prove these results, we design new algorithms and prove conditional lower bounds based on standard hypotheses from fine-grained complexity theory. For our algorithms we introduce a new ingredient that we call hyper-degree splitting, where we split tuples of nodes into high degree and low degree depending on their number of common neighbors. This technique generalizes the classic high-degree-low-degree approach (which only splits along degrees of single nodes) and is crucial to obtain optimal algorithms. Furthermore, we contribute the simple but fundamental insight that to determine the optimal complexity of some natural families of algorithms and lower bounds it suffices to study graphs without clique separators (i.e., cliques whose removal disconnects the pattern graph). This insight immediately implies some existing results in the area and is crucial to obtain a complete classification.