Abstract | A constraint network is arc consistent if any value of any of its variables is compatible with at
least one value of any other variable. The Arc Consistency Problem (ACP) consists in filtering out values of
the variables of a given network to obtain one that is arc consistent, without eliminating any solution. ACP is
known to be inherently sequential, or P-complete, so in this paper we examine some weaker versions of it and
their parallel complexity. We propose several natural approximation schemes for ACP and show that they are also
P-complete. In an attempt to overcome these negative results, we turn our attention to the problem of filtering
out values from the variables so that each value in the resulting network is compatible with at least one value of
not necessarily all, but a constant fraction of the other variables. We call such a network partially arc consistent.
We give a parallel algorithm that, for any constraint network, outputs a partially arc consistent subnetwork of it in
sublinear (O.pn log n/) parallel time using O.n2/ processors. This is the first (to our knowledge) sublinear-time
parallel algorithm with polynomially many processors that guarantees that in the resulting network every value is
compatible with at least one value in at least a constant fraction of the remaining variables. Finally, we generalize
the notion of partiality to the k-consistency problem. |