Enumerating Subgraphs of Constant Sizes in External Memory

We present an indivisible I/O-efficient algorithm for subgraph enumeration, where the objective is to list all the subgraphs of a massive graph G := (V, E) that are isomorphic to a pattern graph Q having k = O(1) vertices. Our algorithm performs (equation presented) I/Os with high probability, where ρ is the fractional edge covering number of Q (it always holds ρ ≥ k/2, regardless of Q), M is the number of words in (internal) memory, and B is the number of words in a disk block. Our solution is optimal in the class of indivisible algorithms for all pattern graphs with ρ > k/2. When ρ = k/2, our algorithm is still optimal as long as M/B ≥ (|E|/B)ϵ for any constant ϵ > 0.