# Theory Seminar: Testing Bounded Arboricity

- Speaker:
- Dana Ron (Tel-Aviv University)
- Date:
- Wednesday, 10.1.2018, 12:30
- Place:
- Taub 201

In this work 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.
In terms of the dependence on $n$ and $m$ our bound is optimal
up to poly-logarithmic factors since $\Omega(n/\sqrt{m})$ queries are necessary.
Our techniques include an efficient local simulation for approximating the outcome of a
global (almost) forest-decomposition algorithm.

This is joint work with Talya Eden and Reut Levi