Random walks and forbidden minors. I: An n^1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs

DOI10.1137/19M1245463MaRDI QIDQ3387757zbMATH OpenOpenAlexFDO

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

Publication date 13 January 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

property testingbounded degree graphsminor-free graphs

Mathematics Subject Classification ID

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

Abstract: Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $varepsilonn$ edges from $G$ to make it $H$-minor free (for some small constant $varepsilon>0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an $H$-minor in such a graph. As an application, suppose one must remove $varepsilonn$ edges from a bounded degree graph $G$ to make it planar. This result implies an algorithm, with the same running time, that produces a $K_{3,3}$ or $K_5$ minor in $G$. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to $n^{o(1)}$ factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an $Omega(sqrtn)$ lower bound of Czumaj et al (RSA 2014). Prior to this work, the only graphs $H$ for which non-trivial one-sided property testers were known for $H$-minor freeness are the following: $H$ being a forest or a cycle (Czumaj et al, RSA 2014), $K_{2,k}$, $(kimes2)$-grid, and the $k$-circus (Fichtenberger et al, Arxiv 2017).

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 II
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• Every minor-closed property of sparse graphs is testable
• Planar graphs: random walks and bipartiteness testing

Cites work

• scientific article; zbMATH DE number 1380616 (Why is no real title available?)
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• A sublinear bipartiteness tester for bounded degree graphs
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• An efficient partitioning oracle for bounded-treewidth graphs
• An expansion tester for bounded degree graphs
• Efficient Planarity Testing
• Every minor-closed property of sparse graphs is testable
• Finding cycles and trees in sublinear time
• Graph minor theory
• Graph minors. XX: Wagner's conjecture
• Graph theory
• Introduction to Property Testing
• Local Graph Partitions for Approximation and Testing
• Noise tolerance of expanders and sublinear expansion reconstruction
• On testing expansion in bounded-degree graphs
• Property testing in bounded degree graphs
• Random walks and forbidden minors II
• Subexponential algorithms for unique games and related problems
• Testing Expansion in Bounded-Degree Graphs
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• Testing cluster structure of graphs
• Testing outerplanarity of bounded degree graphs
• Testing the expansion of a graph
• The disjoint paths problem in quadratic time
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(6)

• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Planar graphs: random walks and bipartiteness testing
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• Random walks and forbidden minors II
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Every minor-closed property of sparse graphs is testable

This page was built for publication: Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs

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