A fast new algorithm for weak graph regularity. (3rd September 2019)

• Record Type: Journal Article
• Authors: Fox, Jacob; Lovász, László Miklós; Zhao, Yufei
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 5(2019)
• Page Start: 777
• Page End: 790
• Publication Date: 2019-09-03
• Subjects: Primary 05C85, -- Secondary 05C50, -- 05D99; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548319000075
• Languages: English
• ISSNs: 0963-5483

Abstract

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 .