Deterministic vs non-deterministic graph property testing

DOI10.1007/S11856-014-1096-XzbMATH Open1304.05123arXiv1304.1982OpenAlexW2155726088MaRDI QIDQ480810FDOQ480810

Authors: Lior Gishboliner, Asaf Shapira 

Publication date: 11 December 2014

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

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.

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

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

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)

Cites Work

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

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)