AN EXPANSION TESTER FOR BOUNDED DEGREE GRAPHS

作者：Kale Satyen^*; Seshadhri C

来源：SIAM Journal on Computing, 2011, 40(3): 709-720.

DOI：10.1137/100802980

• sublinear algorithms
• random walks
• graph expansion

We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs, Technical report TR00-020, ECCC, Potsdam, Germany, 2000]. We give a property tester that takes as input a graph with degree bound d, an expansion bound alpha, and a parameter epsilon > 0. The tester accepts the graph with high probability if its expansion is more than alpha, and rejects it with high probability if it is epsilon-far from any graph with expansion alpha' with degree bound d, where alpha' < alpha is a function of alpha. For edge expansion, we obtain alpha' = Omega(alpha(2)/d), and for vertex expansion, we obtain alpha' = Omega(alpha(2)/d(2)). In either case, the algorithm runs in time <(O)over tilde>(n((1+mu))/(2)d(2)/epsilon alpha(2)) for any fixed mu > 0.

• 出版日期2011
• 单位Microsoft