A Characterization of Easily Testable Induced Subgraphs

Abstract

Let ? We settle this question almost completely by showing that, quite surprisingly, for any graph other than the paths of lengths 1,2 and 3, the cycle of length 4, and their complements, no such property tester exists. We further show that a similar result also applies to the case of directed graphs, thus answering a question raised by the authors in [9]. We finally show that the same results hold even in the case of two-sided error property testers. The proofs combine combinatorial, graph-theoretic and probabilistic arguments with results from additive number theory.

Locations

• CiteSeer X (The Pennsylvania State University) - View - PDF
• Combinatorics Probability Computing - View