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

Consider the family of bounded degree graphs in any minor-closed family (suchas planar graphs). Let d be the degree bound and n be the number of vertices ofsuch a graph. Graphs in these classes have hyperfinite decompositions, where,for a sufficiently small \e > 0, one removes \edn edges to get connectedcomponents of size independent of n. An important tool for sublinear algorithmsand property testing for such classes is the partition oracle, introduced bythe seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracleis a local procedure that gives consistent access to a hyperfinitedecomposition, without any preprocessing. Given a query vertex v, the partitionoracle outputs the component containing v in time independent of n. All theanswers are consistent with a single hyperfinite decomposition. The partitionoracle of Hassidim et al. runs in time d^poly(d/\e) per query. They pose theopen problem of whether poly(d/\e)-time partition oracles exist. Levi-Ron(ICALP 2013) give a refinement of the previous approach, to get a partitionoracle that runs in time d^{\log(d/\e)-per query. In this paper, we resolvethis open problem and give \poly(d/\e)-time partition oracles for boundeddegree graphs in any minor-closed family. Unlike the previous line of workbased on combinatorial methods, we employ techniques from spectral graphtheory. We build on a recent spectral graph theoretical toolkit forminor-closed graph families, introduced by the authors to develop efficientproperty testers. A consequence of our result is a poly(d/\e)-query tester forany monotone and additive property of minor-closed families (such as bipartiteplanar graphs). Our result also gives poly(d/\e)-query algorithms for additive{\e}n-approximations for problems such as maximum matching, minimum vertexcover, maximum independent set, and minimum dominating set for these graphfamilies.

Random walks and forbidden minors III: poly(d/{\epsilon})-time partition oracles for minor-free graph classes