Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-046 | 1st April 2019 17:01

Random walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs

RSS-Feed




Revision #1
Authors: Akash Kumar, C. Seshadhri, Andrew Stolman
Accepted on: 1st April 2019 17:01
Downloads: 771
Keywords: 


Abstract:

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.


Paper:

TR19-046 | 1st April 2019 06:10

andom walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs





TR19-046
Authors: Akash Kumar, C. Seshadhri, Andrew Stolman
Publication: 1st April 2019 11:45
Downloads: 857
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint