A fast new algorithm for weak graph regularity. (3rd September 2019) - Fox, Jacob; Lovász, László Miklós; Zhao, Yufei
Abstract: We provide a deterministic algorithm that finds, in ɛ - O (1) n 2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ - 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 ɛn v(H), in time ɛ - O H (1) n 2 .