Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-054 | 25th May 2007 00:00

Testing Properties of Constraint-Graphs


Authors: Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur
Publication: 16th June 2007 19:45
Downloads: 2953


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.

ISSN 1433-8092 | Imprint