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/19M1245463zbMATH Open1506.68075arXiv1805.08187OpenAlexW3114178996MaRDI QIDQ3387757FDOQ3387757

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

Publication date: 13 January 2021

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

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).

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

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

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)

Cites Work

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

Cited In (6)

• 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
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs

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)