Akash Kumar 0003

SODA Conference 2022 Conference Paper

The complexity of testing all properties of planar graphs, and the role of isomorphism

• Sabyasachi Basu
• Akash Kumar 0003
• C. Seshadhri 0001

Consider property testing on bounded degree graphs and let ∊ > 0 denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on ∊. Recent advances in testing minor-freeness have proven that all additive and monotone properties of planar graphs can be tested in poly( ∊ –1 ) queries. Some properties falling outside this class, such as Hamiltonicity, also have a similar complexity for planar graphs. Motivated by these results, we ask: can all properties of planar graphs can be tested in poly( ∊ –1 ) queries? Is there a uniform query complexity upper bound for all planar properties, and what is the “hardest” such property to test? We discover a surprisingly clean and optimal answer. Any property of bounded degree planar graphs can be tested in exp( O ( ∊ –2 )) queries. Moreover, there is a matching lower bound, up to constant factors in the exponent. The natural property of testing isomorphism to a fixed graph requires exp(Ω( ∊ –2 )) queries, thereby showing that (up to polynomial dependencies) isomorphism to an explicit fixed graph is the hardest property of planar graphs. The upper bound is a straightforward adaptation of the Newman-Sohler analysis that tracks dependencies on ∊ more carefully. The main technical contribution is the lower bound construction, which is achieved by a special family of planar graphs that are all mutually far from each other. We can also apply our techniques to get analogous results for bounded treewidth graphs. We prove that all properties of bounded treewidth graphs can be tested in exp( O ( ∊ –1 log ∊ –1 )) queries. Moreover, testing isomorphism to a fixed forest requires exp(Ω( ∊ –1 )) queries.

FOCS Conference 2021 Conference Paper

Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes

• Akash Kumar 0003
• C. Seshadhri 0001
• Andrew Stolman

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and $n$ be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small fraction of edges of the graph controlled by a proximity parameter to get connected components of size independent of $n$. An important tool for sublinear algorithms and property testing for such classes is the partition oracle, introduced by the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. The partition oracle of Hassidim et al. runs in time exponential in the proximity parameter per query. They pose the open problem of whether partition oracles which run in time polynomial in reciprocal of proximity parameter can be built. Levi-Ron (ICALP 2013) give a refinement of the previous approach, to get a partition oracle that runs in quasipolynomial time per query. In this paper, we resolve this open problem and give polynomial time partition oracles (in reciprocal of proximity parameter) for bounded degree graphs in any minor-closed family. Unlike the previous line of work based on combinatorial methods, we employ techniques from spectral graph theory. We build on a recent spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to develop efficient property testers. A consequence of our result is an efficient property tester for any monotone and additive with running time property of minor-closed families (such as bipartite planar graphs). Our result also gives query efficient algorithms for additive approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families.

STOC Conference 2019 Conference Paper

Random walks and forbidden minors II: a poly( d ε -1 )-query tester for minor-closed properties of bounded degree graphs

• Akash Kumar 0003
• C. Seshadhri 0001
• Andrew Stolman

FOCS Conference 2018 Conference Paper

Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

• Akash Kumar 0003
• C. Seshadhri 0001
• Andrew Stolman

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove ε n edges from G to make it H-minor free (for some small constant ε > 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 ε n 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 Ω(√n) 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, (k× 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).