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

@article{Basu2021TheCO, title={The complexity of testing all properties of planar graphs, and the role of isomorphism}, author={Sabyasachi Basu and Akash Kumar and Seshadhri Comandur}, journal={Electron. Colloquium Comput. Complex.}, year={2021}, volume={28}, pages={122} }

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(ε) queries. Some properties falling outside this class, such as Hamiltonicity, also… Expand

#### Figures from this paper

#### References

SHOWING 1-10 OF 34 REFERENCES

Every minor-closed property of sparse graphs is testable

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 2008

The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments, to infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. Expand

A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)

- Computer Science
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper. Expand

Property Testing in Bounded Degree Graphs

- Mathematics, Computer Science
- STOC '97
- 1997

This work develops the study of testing graph properties as initiated by Goldreich, Goldwasser and Ron and presents randomized algorithms for testing whether an unknown bounded-degree graph is connected, k -connected (for k>1 ), cycle-free and Eulerian. Expand

A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor

- Mathematics, Computer Science
- ICALP
- 2013

This work gives a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in 1/e, thus improving on the result of Hassidim et al. (Proceedings of FOCS 2009). Expand

Planar Graphs: Random Walks and Bipartiteness Testing

- Mathematics, Computer Science
- 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
- 2011

It is proved that bipartiteness can be tested in constant time, and the study of the testability of properties in arbitrary minor-free graphs is initiated. Expand

Local Graph Partitions for Approximation and Testing

- Mathematics, Computer Science
- 2009 50th Annual IEEE Symposium on Foundations of Computer Science
- 2009

A new tool for approximation and testing algorithms called partitioning oracles, which utilize only local computation to consistently answer queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges, is introduced. Expand

Every property of hyperfinite graphs is testable

- Mathematics, Computer Science
- STOC '11
- 2011

It is shown that the structure of a planar graph on large enough number of vertices, n, and with constant maximum degree d, is determined, up to the modification (insertion or deletion) of at most ε d n edges, by the frequency of k-discs for certain k=k(ε,d) that is independent of the size of the graph. Expand

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

- Computer Science
- Electron. Colloquium Comput. Complex.
- 2021

A consequence of the result is a poly(dε−1)-query tester for any monotone and additive property of minor-closed families (such as bipartite planar graphs) and gives poly( dε −1)- query algorithms for additive εn-approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families. Expand

Open Problems in Property Testing of Graphs

- Computer Science
- Electron. Colloquium Comput. Complex.
- 2021

A few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks, and the vast lack of knowledge with respect to testinggraph properties in the general graph model. Expand

Testing Hamiltonicity (and other problems) in Minor-Free Graphs

- Computer Science
- APPROX-RANDOM
- 2021

The notion of covering partitions oracles is introduced which is a relaxed version of partition oracles and designed as a poly(d/ǫ)-time covering partition oracle for this family of graphs for minor-free unbounded degree graphs. Expand