TR07-054 Authors: Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

Publication: 16th June 2007 19:45

Downloads: 2867

Keywords:

We study a model of graph related formulae that we call

the \emph{Constraint-Graph model}. A

constraint-graph is a labeled multi-graph (a graph where loops

and parallel edges are allowed), where each edge $e$ is labeled

by a distinct Boolean variable and every vertex is

associate with a Boolean function over the variables

that label its adjacent edges. A Boolean assignment to the variables

satisfies the constraint graph if it

satisfies every vertex function. We associate with a

constraint-graph $G$ the property of all assignments satisfying

$G$, denoted $SAT(G)$.

We show that the above model is quite general. That is, for every

property of strings ${\cal P}$ there exists a property of

constraint-graphs ${\cal P}_G$ such that ${\cal P}$ is testable

using $q$ queries iff ${\cal P}_G$ is thus testable. In addition,

we present a large family of constraint-graphs for which $SAT(G)$ is

testable with constant number of queries. As an implication of this,

we infer the testability of some edge coloring problems (e.g. the

property of two coloring of the edges in which every node is adjacent

to at least one vertex of each color). Another implication is that every

property of Boolean strings that can be represented by a

Read-twice CNF formula is testable. We note that this is the best possible

in terms of the number

of occurrences of every variable in a formula.