Property Testing of Massively Parametrized problems -- A survey <s> Testing H-freeness <s> Let H be a fixed graph with h vertices, let G be a graph on n vertices and suppose that at least /spl epsi/n/sup 2/ edges have to be deleted from it to make it H-free. It is known that in this case G contains at least f (/spl epsi/, H)n/sup h/ copies of H. We show that the largest possible function f (/spl epsi/, H) is polynomial in /spl epsi/ if and only if H is bipartite. This implies that there is a one-sided error property tester for checking H-freeness, whose query complexity is polynomial in 1//spl epsi/, if and only if H is bipartite. <s> BIB001 </s> Property Testing of Massively Parametrized problems -- A survey <s> Testing H-freeness <s> We propose a new model for studying graph related problems that we call the orientation model. In this model, an undirected graph G is xed, and the input is any possible edge orientation of G. A property is now a property of the directed graph that is obtained by a given orientation. The distance between two orientations is the number of edges that have to be redirected in order to move from one digraph to the other. This model allows studying digraph properties such as not containing a forbidden (induced) subgraph, being strongly connected etc., for every underlying graph including sparse graphs. As it turns out, this model generalizes the standard, adjacency matrix model. That is, we show that for every graph property P of dense graphs there is a property of orientations that is testable if and only if P is. This model is also handy in some practical situations of networks, in which the underlying network is xed while the direction of (weighted) links may vary. We show that several orientations properties are testable in this model (for every underlying graph), while some are not. <s> BIB002 </s> Property Testing of Massively Parametrized problems -- A survey <s> Testing H-freeness <s> For a Boolean formula $\phi$ on n variables, the associated property $P_\phi$ is the collection of n-bit strings that satisfy $\phi$. We study the query complexity of tests that distinguish (with high probability) between strings in $P_\phi$ and strings that are far from $P_\phi$ in Hamming distance. We prove that there are 3CNF formulae (with O(n) clauses) such that testing for the associated property requires $\Omega(n)$ queries, even with adaptive tests. This contrasts with 2CNF formulae, whose associated properties are always testable with $O(\sqrt{n})$ queries [E. Fischer et al., Monotonicity testing over general poset domains, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 474--483]. Notice that for every negative instance (i.e., an assignment that does not satisfy $\phi$) there are three bit queries that witness this fact. Nevertheless, finding such a short witness requires reading a constant fraction of the input, even when the input is very far from satisfying the formula that is associated with the property. ::: A property is linear if its elements form a linear space. We provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include the following observations which are of independent interest: ::: In the context of testing for linear properties, adaptive two-sided error tests have no more power than nonadaptive one-sided error tests. Moreover, without loss of generality, any test for a linear property is a linear test. A linear test verifies that a portion of the input satisfies a set of linear constraints, which define the property, and rejects if and only if it finds a falsified constraint. A linear test is by definition nonadaptive and, when applied to linear properties, has a one-sided error. ::: Random low density parity check codes (which are known to have linear distance and constant rate) are not locally testable. In fact, testing such a code of length n requires $\Omega(n)$ queries. <s> BIB003
Let H = (V H , E H ) be a fixed directed graph. The digraph property of H-freeness contains all digraphs that do not have a subgraph isomorphic to H, and is denoted by F H (G). A sink in a digraph is a vertex v for which d out (v) = 0, namely, has no outgoing edges. Similarly v is a source if d in (v) = 0. A graph is source-free (analogously sink-free) if it contains no source. The following Theorem is proved in BIB002 . Theorem 1 BIB002 Let H be a fixed digraph that is either source-free or sink-free. Then, for any O(1)-bounded degree graph G and > 0, there is a 1-sided error -test for F H (G) making poly(1/ ) queries. Proof. (Sketch.) Assume w.l.o.g that H is source-free. To make a G-orientation G, H-free, one can pick a vertex v from each copy of H in G and reorient all edges so to make v a source. Obviously this should be done sequentially picking no two adjacent vertices. This implies that if G is -far from being H-free, every subset C ⊆ V that hits all copies of H in G must have |C| = Ω(n). Hence, sampling a random vertex and checking its neighborhood of size |H| to discover if it belongs to a H-copy (and reject if it does) is a test for H-freeness. Note that the test relies on the fact that G is of bounded degree and that H is either source free or sink free. One may wonder whether these conditions are truly necessary. We first address the issue of being either source or sink free. The simplest interesting digraph H that has both a source and a sink is P 2 , the path of length 2 on 3 vertices (every digraph with non-empty edge set is not P 1 -free). Testing P 2 -freeness is easy since a G-orientation is P 2 -free if and only if G is bipartite G = (X, Y ; E) and all its edges are oriented, say, from X to Y . Thus sampling a random edge is a good test. Going however one step further, it is shown in BIB002 that testing P 3 -freeness requires a linear number of queries for some bounded degree graphs. The reduction is from testing whether a 3-coloring of a 3-colorable graph is indeed a proper coloring, which is shown to require a linear number of queries (implicit in BIB003 ). Regarding the degree restriction, we don't know if this restriction is absolutely required, however, BIB002 observed: Let C 6 be the directed cycle on 6 vertices. Observation 4.1 BIB002 There exists an infinite family of graphs, each with O(1)-average degree, for which every 1-sided error -test for the G-orientation property of C 6 -freeness makes (1/ ) queries. The proof is immediate: testing triangle-freeness in the dense graph model is reducible to testing C 6 -freeness in the orientation model where the underlying graph is a subdivided K n . The result of BIB001 completes the proof.