Testing whether a digraph contains H-free k-induced subgraphs

AbstractA 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 Ω(N2)-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 ϵ-tester is independent of the size of the input digraph. An (ϵ,δ)-tester for a property Π is an ϵ-tester for Π that is furthermore guaranteed to accept with probability at least 2/3 any input that is δ-close to satisfying Π. This paper presents an (ϵ,δ)-tester for whether a digraph contains H-free k-induced subgraphs