Deterministic vs non-deterministic graph property testing

DOI10.1007/S11856-014-1096-XMaRDI QIDQ480810zbMATH OpenOpenAlexFDO

Authors Lior Gishboliner, Asaf Shapira

Publication date 11 December 2014

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1982

zbMATH Keywords

nondeterministic testing of graphSzemerédi's regularity lemma

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P so that once the certificate is given its correctness can be tested. The notion of non-deterministic testing of graph properties was recently introduced by Lovasz and Vesztergombi, who proved that (somewhat surprisingly) a graph property is testable if and only if it is non-deterministically testable. Their proof used graph limits, and so it did not supply any explicit bounds. They thus asked if one can obtain a proof of their result which will supply such bounds. We answer their question positively by proving their result using Szemeredi's regularity lemma. An interesting aspect of our proof is that it highlights the fact that the regularity lemma can be interpreted as saying that all graphs can be approximated by finitely many "template" graphs.

Recommendations

• Non-deterministic graph property testing
• Efficient testing of large graphs
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Every monotone graph property is testable
• Every Monotone Graph Property Is Testable

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Efficient testing of large graphs
• Non-deterministic graph property testing
• Property testing and its connection to learning and approximation
• Property testing. Current research and surveys
• Sublinear time algorithms
• Testing properties of graphs and functions
• Testing versus Estimation of Graph Properties
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• Three theorems regarding testing graph properties

Cited in

(3)

• Non-interactive proofs of proximity
• Hyper resolution and equality axioms without function substitutions
• Non-deterministic graph property testing

This page was built for publication: Deterministic vs non-deterministic graph property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q480810)