## Abstract

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_{2}) 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.

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

Title of host publication | Foundations of Software Technology and Theoretical Computer Science - 15th Conference, Proceedings |

Editors | P.S. Thiagarajan |

Publisher | Springer Verlag |

Pages | 210-224 |

Number of pages | 15 |

ISBN (Print) | 3540606920, 9783540606925 |

DOIs | |

State | Published - 1995 |

Event | 15th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1995 - Bangalore, India Duration: Dec 18 1995 → Dec 20 1995 |

### Publication series

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

Volume | 1026 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1995 |
---|---|

Country/Territory | India |

City | Bangalore |

Period | 12/18/95 → 12/20/95 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science