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

A subgraph induced by vertices is called a -induced subgraph. We prove that determining if a digraph contains -free -induced subgraphs is -evasive. Then we construct an -tester to test this property. (An -tester for a property is guaranteed to distinguish, with probability at least , between the case of satisfying and the case of 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 any input that is -close to satisfying . This paper presents an -tester for whether a digraph contains -free -induced subgraphs.