A fast new algorithm for weak graph regularity

Abstract

We provide a deterministic algorithm that finds, in ${\epsilon }^{-O(1)}{n}^2$ time, an $\epsilon$-regular Frieze-Kannan partition of a graph on $n$ vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ${\epsilon }^{-O(1)}$ many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of $H$ in an $n$-vertex graph $G$ up to an additive error of at most $\epsilon n^{v(H)}$, in time ${\epsilon }^{-O_H(1)}{n}^2$.

12 pages, not including references. arXiv admin note: text overlap with arXiv:1604.00733

References in corpus (1)

• On regularity lemmas and their algorithmic applications