Talya Eden
Testing Bounded Arboricity

Abstract: In this paper we consider the problem of tolerantly 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. 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. Our algorithm distinguishes between graphs that are -close
to having arboricity and graphs that are -far from having arboricity
at most , for some small absolute constant .