Partiality and approximation schemes for local consistency in networks of constraints

A constraint network is arc consistent if any value 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, i.e. a total value assignment that satisfies all constraints. Enforcing arc consistency, or the more general κ-consistency, in a constraint network is a widely used preprocessing step before identifying the set of solutions. ACP is known to be inherently sequential, so in this paper we examine the problem of achieving partial consistency, i.e. filtering out values from the variables so that each value in the new network is compatible with at least one value of not necessarily all, but a constant fraction of the other variables. We call such networks partially arc consistent. We give an algorithm that, for any constraint network, outputs a partially arc consistent subnetwork of it in sublin- ear [formula presented] parallel time using O(n₂) processors. This is the first (to our knowledge) sublinear-time parallel algorithm with polynomially many processors that removes at least a constant fraction of the local inconsistencies of a general constraint network, without eliminating any solution. We also generalize the notion of partiality to the κ-consistency problem: We give an algorithm that is faster than the previously known κ-consistency algorithms, and which finds a partially κ-consistent sub network of any given network. Finally, we propose several approximation schemes to a total solution of ACP, and show that they are P-complete. This indicates that the approach of partial solutions, rather than that of approximation schemes, is more promising for parallelism.