zbMATH — the first resource for mathematics

An expansion tester for bounded degree graphs. (English) Zbl 1153.68466
Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 527-538 (2008).
Summary: We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model. We give a property tester that given a graph with degree bound \(d\), an expansion bound \(\alpha \), and a parameter \(\epsilon > 0\), 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 ^{\prime}\) with degree bound \(d\), where \(\alpha ^{\prime} < \alpha \) is a function of \(\alpha \). For edge expansion, we obtain \(\alpha' = \Omega(\frac{\alpha^2}{d})\), and for vertex expansion, we obtain \(\alpha' = \Omega(\frac{\alpha^2}{d^2})\). In either case, the algorithm runs in time \(\tilde{O}(\frac{n^{(1+\mu)/2}d^2}{\epsilon\alpha^2})\) for any given constant \(\mu > 0\).
For the entire collection see [Zbl 1142.68001].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Full Text: DOI