A fast new algorithm for weak graph regularity

DOI10.1017/S0963548319000075MaRDI QIDQ5222555zbMATH OpenOpenAlexFDO

Authors Jacob Fox, László Miklós Lovász, Yufei Zhao

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.05037

zbMATH Keywords

edge densityregularity method

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99)

Abstract: We provide a deterministic algorithm that finds, in $epsilo{n}^{-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 $epsilo{n}^{-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 $epsilo{n}^{-O_H(1)}{n}^2$.

Recommendations

• An Algorithmic Version of the Hypergraph Regularity Method
• Algorithms for weakly triangulated graphs
• The graph regularity method: variants, applications, and alternative methods
• An algorithmic hypergraph regularity lemma
• An Algorithmic Hypergraph Regularity Lemma
• On the complexity of identifying strongly regular graphs
• Improved algorithms for weakly chordal graphs
• An Algorithmic Regularity Lemma for Hypergraphs

Cites work

• A deterministic algorithm for the Frieze-Kannan regularity lemma
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• An Optimal Algorithm for Checking Regularity
• An optimal algorithm for finding Frieze-Kannan regular partitions
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Erratum to: ``On regularity lemmas and their algorithmic applications
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Explicit constructions of linear-sized superconcentrators
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• On regularity lemmas and their algorithmic applications
• On sets of integers containing k elements in arithmetic progression
• Quick approximation to matrices and applications
• Ramanujan graphs
• Szemerédi's lemma for the analyst
• The Algorithmic Aspects of the Regularity Lemma

Cited in

(7)

• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Improved algorithms for weakly chordal graphs
• An Optimal Algorithm for Checking Regularity
• Amplification and Derandomization without Slowdown
• An optimal algorithm for finding Frieze-Kannan regular partitions
• The sparse regularity method with Schatten norms and entropy
• Efficient polynomial-time approximation scheme for the genus of dense graphs

This page was built for publication: A fast new algorithm for weak graph regularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222555)