A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph

Abstract

In this paper we give an algorithm which, given a labeled graph on n vertices and a list of all labeled graphs on k vertices, provides for each graph H of this list an approximation to the number of induced copies of H in G with total error small. This algorithm has running time $O(n^{1/ \log \log n} \cdot M(n))$, where $M(n)$ is the time needed to square an n by n matrix with 0, 1-entries over the integers. The main tool in designing this algorithm is a variant of the regularity lemma of Szemerédi.