2021/01/31 by Akash Kumar, Kumar, Akash, C. Seshadhri +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2102.00556
openalex publication_date 2021/01/31 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Consider the family of bounded degree graphs in any minor-closed family (such\nas planar graphs). Let d be the degree bound and n be the number of vertices of\nsuch a graph. Graphs in these classes have hyperfinite decompositions, where,\nfor a sufficiently small e > 0, one removes edn edges to get connected\ncomponents of size independent of n. An important tool for sublinear algorithms\nand property testing for such classes is the partition oracle, introduced by\nthe seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle\nis a local procedure that gives consistent access to a hyperfinite\ndecomposition, without any preprocessing. Given a query vertex v, the partition\noracle outputs the component containing v in time independent of n. All the\nanswers are consistent with a single hyperfinite decomposition. The partition\noracle of Hassidim et al. runs in time dpoly(d/ e) per query. They pose the\nopen problem of whether poly(d/ e)-time partition oracles exist. Levi-Ron\n(ICALP 2013) give a refinement of the previous approach, to get a partition\noracle that runs in time d^\log(d/ e)-per query. In this paper, we resolve\nthis open problem and give poly(d/ e)-time partition oracles for bounded\ndegree graphs in any minor-closed family. Unlike the previous line of work\nbased on combinatorial methods, we employ techniques from spectral graph\ntheory. We build on a recent spectral graph theoretical toolkit for\nminor-closed graph families, introduced by the authors to develop efficient\nproperty testers. A consequence of our result is a poly(d/ e)-query tester for\nany monotone and additive property of minor-closed families (such as bipartite\nplanar graphs). Our result also gives poly(d/ e)-query algorithms for additive\n en-approximations for problems such as maximum matching, minimum vertex\ncover, maximum independent set, and minimum dominating set for these graph\nfamilies.\n