Revision #1 Authors: Akash Kumar, C. Seshadhri, Andrew Stolman

Accepted on: 1st April 2019 17:01

Downloads: 538

Keywords:

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).

We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.

The problem of property testing $\mathcal{P}$ was introduced in the seminal work of Benjamini-Schramm-Shapira (STOC 2008)

that gave a tester with query complexity triply exponential in $\varepsilon^{-1}$.

Levi-Ron (TALG 2015) have given the best tester to date, with a quasipolynomial (in $\varepsilon^{-1}$) query complexity.

It is an open problem to get property testers whose query complexity is $\poly(d\varepsilon^{-1})$,

even for planarity.

In this paper, we resolve this open question. For any minor-closed property,

we give a tester with query complexity $d\cdot \poly(\varepsilon^{-1})$.

The previous line of work on (independent of $n$, two-sided) testers is primarily combinatorial.

Our work, on the other hand, employs techniques from spectral graph theory. This paper

is a continuation of recent work of the authors (FOCS 2018) analyzing random walk algorithms

that find forbidden minors.

TR19-046 Authors: Akash Kumar, C. Seshadhri, Andrew Stolman

Publication: 1st April 2019 11:45

Downloads: 609

Keywords:

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).

We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.

The problem of property testing $\mathcal{P}$ was introduced in the seminal work of Benjamini-Schramm-Shapira (STOC 2008)

that gave a tester with query complexity triply exponential in $\varepsilon^{-1}$.

Levi-Ron (TALG 2015) have given the best tester to date, with a quasipolynomial (in $\varepsilon^{-1}$) query complexity.

It is an open problem to get property testers whose query complexity is $\poly(d\varepsilon^{-1})$,

even for planarity.

In this paper, we resolve this open question. For any minor-closed property,

we give a tester with query complexity $d\cdot \poly(\varepsilon^{-1})$.

The previous line of work on (independent of $n$, two-sided) testers is primarily combinatorial.

Our work, on the other hand, employs techniques from spectral graph theory. This paper

is a continuation of recent work of the authors (FOCS 2018) analyzing random walk algorithms

that find forbidden minors.