A subgraph induced by k vertices is called a k-induced subgraph. We prove that determining if a digraph G contains H-free k-induced subgraphs is Ω(N{sup}2)-evasive. Then we construct an ε-tester to test this property. (An ε-tester for a property ? is guaranteed to distinguish, with probability at least 2/3, between the case of G satisfying ? and the case of G being ε-far from satisfying ?.) The query complexity of the e-tester is independent of the size of the input digraph. An (ε, δ)-tester for a property ? is an e-tester for ? that is furthermore guaranteed to accept with probability at least 2/3 any input that is δ-close to satisfying 77. This paper presents an (ε, δ)-tester for whether a digraph contains H-free k-induced subgraphs.
展开▼
