## Abstract

A constraint network is arc consistent if any value of its variables is compatible with at least one value of any other variable. Enforcing arc consistency in a constraint network is a commonly used preprocessing step before identifying the globally consistent value assignments to all the variables. Since many constraint networks that arise in practice are overconstrained, any global assignment of values to the variables involved, is expected to include constraint violations. Therefore, it is often necessary to enforce some weak form of consistency, to avoid excessive value elimination due to the existence of many constraints. It is also necessary that this form of consistency be enforced fast. In this paper, we introduce a notion of weak local consistency that we call partial arc consistency. We then give an algorithm that, for any constraint network of n variables, outputs a partially arc consistent subnetwork of it in sublinear (0(√nlog n)) parallel time using 0(n^{2}) processors. This algorithm removes at least a constant fraction of the local inconsistencies of a general constraint network, without eliminating any globally consistent assignment of values. To our knoweldge, it is the first sublinear-time parallel algorithm with polynomially many processors that achieves this extent of local consistency. Moreover, we propose several approximation schemes to a total solution of the arc consistency problem. We show that these approximation schemes are inherently sequential (more formally, they are P-complete), a fact indicating that the approach of partial solutions, rather than that of approximation schemes, is more promising for parallelism.

Original language | English (US) |
---|---|

Title of host publication | Over-Constrained Systems |

Editors | Michael Jampel, Eugene Freuder, Michael Maher |

Publisher | Springer Verlag |

Pages | 229-236 |

Number of pages | 8 |

ISBN (Print) | 3540614796, 9783540614791 |

DOIs | |

State | Published - 1996 |

Event | Workshop on Over-Constrained Systems, held as part of 1st International Conference on Principles and Practice of Constraint Programming, CP 1995 - Marseilles, France Duration: Sep 18 1995 → Sep 18 1995 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1106 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Workshop on Over-Constrained Systems, held as part of 1st International Conference on Principles and Practice of Constraint Programming, CP 1995 |
---|---|

Country/Territory | France |

City | Marseilles |

Period | 9/18/95 → 9/18/95 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science