We consider the problem of testing whether a graph has bounded arboricity.
The family of graphs with bounded arboricity includes, among others, bounded-degree graphs, all minor-closed graph classes (e.g. planar graphs, graphs with bounded treewidth) and randomly generated preferential attachment graphs.
Graphs with bounded arboricity have been studied extensively in the past, in particular since for many problems they allow for much more efficient algorithms and/or better approximation ratios.
We present a tolerant tester in the sparse-graphs model. The sparse-graphs model allows access to degree queries and neighbor queries, and the distance is defined with respect to the actual number of edges.
More specifically, our algorithm distinguishes between graphs that are $\epsilon$-close to having arboricity $\alpha$ and graphs that are $c \cdot \epsilon$-far from having arboricity $3\alpha$, where $c$ is an absolute small constant.
The expected query complexity and running time of the algorithm are $\tilde{O}(\frac{n}{\eps \sqrt{m}}+(\frac{1}{\epsilon})^{O(\log(1/\epsilon))})$ where $n$ denotes the number of vertices and $m$ denotes the number of edges.
In terms of the dependence on $n$ and $m$ this bound is optimal up to poly-logarithmic factors since $\Omega(n/\sqrt{m})$ queries are necessary.
We leave it as an open question whether the dependence on $1/\epsilon$ can be improved from quasi-polynomial to polynomial.
Our techniques include an efficient local simulation for approximating the outcome of a global (almost) forest-decomposition algorithm.
This is a joint work with Talya Eden and Dana Ron.
Reut Levi is a postdoctoral scholar at the Faculty of Mathematics and
Computer Science of Weizmann Institute of Science, Israel. Previously she was a postdoctoral scholar at Max Planck Institute for Informatics in Germany, École Normale Supérieure and
Université Paris Diderot - Paris 7 in France. She graduated her B.Sc. studies in Bioinformatics and her M.Sc. studies in Computer Science with honors at Tel-Aviv University. She completed her Ph.D. in Computer Science at Tel-Aviv University under supervision of Prof. Dana Ron and Prof. Ronitt Rubinfeld. Her research interests include Sublinear Algorithms, Property Testing and Local Computation Algorithms.