ECCC-Report TR07-054https://eccc.weizmann.ac.il/report/2007/054Comments and Revisions published for TR07-054en-usSat, 16 Jun 2007 19:45:50 +0300
Paper TR07-054
| Testing Properties of Constraint-Graphs |
Shirley Halevy,
Oded Lachish,
Ilan Newman,
Dekel Tsur
https://eccc.weizmann.ac.il/report/2007/054We 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.
Sat, 16 Jun 2007 19:45:50 +0300https://eccc.weizmann.ac.il/report/2007/054