Random walks and forbidden minors II

DOI10.1145/3313276.3316330MaRDI QIDQ5212798zbMATH OpenOpenAlexFDO

Authors A. Kumar, C. Seshadhri, Andrew M. Stolman

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.01055

zbMATH Keywords

bounded-degree graphsgraph minorsproperty testing

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph minors (05C83) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $mathcalP$ (such as planarity). We say that $G$ is $varepsilon$-far from $mathcalP$ if one has to remove $varepsilondn$ edges to make it have $mathcalP$. The problem of property testing $mathcalP$ was introduced in the seminal work of Benjamini-Schramm-Shapira (STOC 2008) that gave a tester with query complexity triply exponential in $varepsilo{n}^{-1}$. Levi-Ron (TALG 2015) have given the best tester to date, with a quasipolynomial (in $varepsilo{n}^{-1}$) query complexity. It is an open problem to get property testers whose query complexity is $extpoly(dvarepsilo{n}^{-1})$, even for planarity. In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexity $dcdotextpoly(varepsilo{n}^{-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.

Recommendations

• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• On random graphs from a minor-closed class
• Random graphs from a minor-closed class
• The complexity of minor-ancestral graph properties with forbidden pairs
• A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
• Bounds on the number of closed walks in a graph and its applications
• Random graphs from a weighted minor-closed class
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width

Cited in

(12)

• On the tree-width of even-hole-free graphs
• Property testing of planarity in the \textsf{CONGEST} model
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Multiple random walks on graphs: mixing few to cover many
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Planarity via spanning tree number: a linear-algebraic criterion
• Pliability and approximating Max-CSPs
• Multiple random walks on graphs: mixing few to cover many
• Every minor-closed property of sparse graphs is testable

This page was built for publication: Random walks and forbidden minors II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212798)