A fast new algorithm for weak graph regularity

DOI10.1017/S0963548319000075zbMATH Open1436.05106arXiv1801.05037OpenAlexW3104055895MaRDI QIDQ5222555FDOQ5222555

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)

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$.

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

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

zbMATH Keywords

regularity methodedge density

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• An optimal algorithm for finding Frieze-Kannan regular partitions
• An Optimal Algorithm for Checking Regularity
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Improved algorithms for weakly chordal graphs
• Amplification and Derandomization without Slowdown

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)