English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix afinite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ tomake 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$\varepsilon n$ edges from a bounded degree graph $G$ to make it planar. Thisresult 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 forthis problem.  By the graph minor theorem, we get an analogous result for any minor-closedproperty. Up to $n^{o(1)}$ factors, this resolves a conjecture ofBenjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided propertytesters for minor-closed properties. Furthermore, our algorithm is nearlyoptimal, by an $\Omega(\sqrt{n})$ lower bound of Czumaj et al (RSA 2014).  Prior to this work, the only graphs $H$ for which non-trivial one-sidedproperty testers were known for $H$-minor freeness are the following: $H$ beinga forest or a cycle (Czumaj et al, RSA 2014), $K_{2,k}$, $(k\times 2)$-grid,and the $k$-circus (Fichtenberger et al, Arxiv 2017).

Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs