Testing small set expansion in general graphs

DOI10.4230/LIPICS.STACS.2015.622MaRDI QIDQ2955028zbMATH OpenOpenAlexFDO

Authors Pan Peng, Angsheng Li

Publication date 24 January 2017

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

zbMATH Keywords

spectral graph theoryrandom walkssmall set expansiongraph property testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Graph operations (line graphs, products, etc.) (05C76) Random walks on graphs (05C81)

Abstract: We consider the problem of testing small set expansion for general graphs. A graph $G$ is a $(k,phi)$-expander if every subset of volume at most $k$ has conductance at least $phi$. Small set expansion has recently received significant attention due to its close connection to the unique games conjecture, the local graph partitioning algorithms and locally testable codes. We give testers with two-sided error and one-sided error in the adjacency list model that allows degree and neighbor queries to the oracle of the input graph. The testers take as input an $n$-vertex graph $G$, a volume bound $k$, an expansion bound $phi$ and a distance parameter $varepsilon>0$. For the two-sided error tester, with probability at least $2/3$, it accepts the graph if it is a $(k,phi)$-expander and rejects the graph if it is $varepsilon$-far from any $(k^{\ast },ph{i}^{\ast })$-expander, where $k^{\ast }=Theta(kvarepsilon)$ and $ph{i}^{\ast }=Theta(fracph{i}^{4}minlog(4m/k),logncdot(lnk))$. The query complexity and running time of the tester are $widetildeO(sqrtmph{i}^{-4}varepsilo{n}^{-2})$, where $m$ is the number of edges of the graph. For the one-sided error tester, it accepts every $(k,phi)$-expander, and with probability at least $2/3$, rejects every graph that is $varepsilon$-far from $(k^{\ast },ph{i}^{\ast })$-expander, where $k^{\ast }=O(k^{1-xi})$ and $ph{i}^{\ast }=O(xiph{i}^2)$ for any $0<xi<1$. The query complexity and running time of this tester are $widetildeO(sqrtfracnvarepsilo{n}^3+frackvarepsilonph{i}^4)$. We also give a two-sided error tester with smaller gap between $ph{i}^{\ast }$ and $phi$ in the rotation map model that allows (neighbor, index) queries and degree queries.

Recommendations

• An expansion tester for bounded degree graphs
• An Expansion Tester for Bounded Degree Graphs
• Testing the expansion of a graph
• Testing Expansion in Bounded-Degree Graphs
• On testing expansion in bounded-degree graphs

Cited in

(5)

• Graph expansion and the unique games conjecture
• Testing the expansion of a graph
• Gap amplification for small-set expansion via random walks
• A two-sided error distributed property tester for conductance
• Testing Expansion in Bounded-Degree Graphs

This page was built for publication: Testing small set expansion in general graphs

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