ECCC-Report TR19-046https://eccc.weizmann.ac.il/report/2019/046Comments and Revisions published for TR19-046en-usMon, 01 Apr 2019 17:01:12 +0300
Revision 1
| Random walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs |
Akash Kumar,
C. Seshadhri,
Andrew Stolman
https://eccc.weizmann.ac.il/report/2019/046#revision1Let $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.
Mon, 01 Apr 2019 17:01:12 +0300https://eccc.weizmann.ac.il/report/2019/046#revision1
Paper TR19-046
| andom walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs |
Akash Kumar,
C. Seshadhri,
Andrew Stolman
https://eccc.weizmann.ac.il/report/2019/046Let $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.
Mon, 01 Apr 2019 11:45:13 +0300https://eccc.weizmann.ac.il/report/2019/046